Paper by Erik D. Demaine

Reference:

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.

Abstract:

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^δ log² n log m) (for any δ > 0) using O(4^1/δ) passes/rounds while achieving an approximation factor of O(4^1/δ 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(4^1/δ). 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.

Availability:

Currently unavailable. If you are in a rush for copies, contact me.

[Google Scholar search]