Better Streaming Algorithms for the Maximum Coverage Problem
Andrew McGregor, Hoa T. Vu · Theory of Computing Systems · 2018
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 \}\) , find the k sets that cover the most number of distinct elements. The problem can be approximated up to a factor \(1-1/e\) in polynomial time. In the streaming-set model, the sets and their elements are revealed online. The main goal of our work is to design algorithms, with approximation guarantees as close as possible to \(1-1/e\) , that use sublinear space \(o(mn)\) . Our main results are: Two \((1-1/e-\epsilon )\) approximation algorithms: One uses \(O(\epsilon ^{-1})\) passes and \(\tilde {O}(\epsilon ^{-2} k)\) space whereas the other uses only a single pass but \(\tilde {O}(\epsilon ^{-2} m)\) space. \(\tilde {O}(\cdot )\) suppresses polylog factors. We show that any approximation factor better than \((1-(1-1/k)^{k})\approx 1-1/e\) in constant passes requires \({\Omega }(m)\) space for constant k even if the algorithm is allowed unbounded processing time. We also demonstrate a single-pass , \((1-\epsilon )\) approximation algorithm using \(\tilde {O}\left (\epsilon ^{-2} m \cdot \min (k,\epsilon ^{-1})\right )\) space. We also study the maximum k -vertex coverage problem in the dynamic graph stream model. In this model, the stream consists of edge insertions and deletions of a graph on N vertices. The goal is to find k vertices that cover the most number of distinct edges. We show that any constant approximation in constant passes requires \({\Omega }(N)\) space for constant k whereas \(\tilde {O}(\epsilon ^{-2}N)\) space is sufficient for a \((1-\epsilon )\) approximation and arbitrary k in a single pass. For regular graphs, we show that \(\tilde {O}(\epsilon ^{-3}k)\) space is sufficient for a \((1-\epsilon )\) approximation in a single pass. We generalize this to a \((\kappa -\epsilon )\) approximation when the ratio between the minimum and maximum degree is bounded below by \(\kappa \) .