**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^{2}*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]

See also other papers by Erik Demaine.

Last updated February 26, 2024 by Erik Demaine.