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,
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated October 28, 2020 by