Advertisement
Published in:
2014 | OriginalPaper | Chapter
On Streaming and Communication Complexity of the Set Cover Problem
Authors : Erik D. Demaine, Piotr Indyk, Sepideh Mahabadi, Ali Vakilian
Published in: Distributed Computing
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
) using
O
(4
1/
δ
) passes/rounds while achieving an approximation factor of
O
(4
1/
δ
log
n
) in polynomial time (for
δ
= Ω(1/log
n
)). 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.