On Streaming and Communication Complexity of the Set Cover Problem
Lists
Only you see this
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 δ log2 n logm) using O(41/δ ) passes/rounds while achieving an approximation factor of O(41/δ logn) in polynomial time (for δ = Ω(1/logn)). 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.
BibTeX
@inproceedings{demaine2014streaming,
author = {Erik D. Demaine and Piotr Indyk and Sepideh Mahabadi and Ali Vakilian},
title = {{On Streaming and Communication Complexity of the Set Cover Problem}},
booktitle = {DISC},
year = {2014},
doi = {10.1007/978-3-662-45174-8\_33},
}Loading related content...