Tight Trade-offs for the Maximum k-Coverage Problem in the General Streaming Model
Piotr Indyk, Ali Vakilian · 2019
We study the maximum k-coverage problem in the general edge-arrival streaming model: given a collection of m sets F, each subset of a ground set of elements U of size n, the task is to find k sets whose coverage is maximized. The sets are specified as a sequence of (element, set) pairs in an arbitrary order. Our main result is a tight (up to polylogarithmic factors) trade-off between the space complexity and the approximation factor α\in(1/(1-1/e), \tildeOmega (\sqrtm )]$ of any single-pass streaming algorithm that estimates the maximum coverage size. Specifically, we show that the optimal space bound is $\tildeTheta (m/α^2)$. Moreover, we design a single-pass algorithm that reports an α-approximate solution in $\tildeO (m/α^2 + k)$ space. Our algorithm heavily exploits data stream sketching techniques, which could lead to further connections between vector sketching methods and streaming algorithms for combinatorial optimization tasks.