Title: On Streaming and Communication Complexity of the Set Cover Problem

Authors: Erik D. Demaine, Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian


Wedevelopthefirststreamingalgorithmandthefirsttwo-partycom- munication protocol that uses a constant number of passes/rounds and sublin- ear space/communication for logarithmic approximation to the classic Set Cover problem. Specifically, for n elements and m sets, our algorithm/protocol achieves a space bound of $O(m · n^δ log^2 n log m)$ using O(4^{1/δ} ) passes/rounds while achieving an approximation factor of $O(4^{1/δ} log n)$ in polynomial time (for $δ = Ω(1/ {log n})$). If we allow the algorithm/protocol to spend exponential time per pass/round, we achieve an approximation factor of O(41/δ). Our approach uses randomization, which we show is necessary: no deterministic constant approxi- mation is possible (even given exponential time) using o(mn) space. These re- sults are some of the first on streaming algorithms and efficient two-party com- munication protocols for approximation algorithms. Moreover, we show that our algorithm can be applied to multi-party communication model.

Full Text: [PDF]

Accessibility at Yale   Inference, Information, and Decision Group at Yale