Paper by Erik D. Demaine

Erik D. Demaine, Piotr Indyk, Sepideh Mahabadi, and Ali Vakilian, “On Streaming and Communication Complexity of the Set Cover Problem”, in Proceedings of the 28th International Symposium on Distributed Computing (DISC 2014), Austin, Texas, October 12–15, 2014, pages 484–498.

We develop the first streaming algorithm and the first two-party communication protocol that uses a constant number of passes/rounds and sublinear 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δ log2 n log m) (for any δ > 0) using O(41/δ) passes/rounds while achieving an approximation factor of O(41/δ log n) in polynomial time. 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 approximation is possible (even given exponential time) using o(m n) space. These results are some of the first on streaming algorithms and efficient two-party communication protocols for approximation algorithms. Moreover, we show that our algorithm can be applied to multi-party communication model.

Currently unavailable. If you are in a rush for copies, contact me.
[Google Scholar search]

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 26, 2017 by Erik Demaine.