Improved Algorithms for Maximum Coverage in Dynamic and Random Order Streams

Amit Chakrabarti, Andrew McGregor, Anthony Wirth

The maximum coverage problem is to select $k$ sets from a collection of sets such that the cardinality of the union of the selected sets is maximized. We consider $(1-1/e-\epsilon )$-appro…