Better Streaming Algorithms for the Maximum Coverage Problem

Andrew McGregor, Hoa T. Vu

We study the classic NP-Hard problem of finding the maximum $k$-set coverage in the data stream model: given a set system of $m$ sets that are subsets of a universe $\{1,\ldots,n \…