On Streaming and Communication Complexity of the Set Cover Problem
On Streaming and Communication Complexity of the Set Cover Problem
复制标题
关于布景覆盖问题的流式传输和通信复杂性
DOI：
10.1007/978-3-662-45174-8_33
复制
发表时间：
2014
影响因子：
0.9
通讯作者：
A. Vakilian
中科院分区：
文献类型：
--
作者：
E. Demaine;P. Indyk;S. Mahabadi;A. Vakilian
我们开发了第一个流算法和第一个两方通信协议，该协议使用恒定数量的通行/弹空间/sublinear空间/通信，用于对数近似值，专门针对经典套装问题。协议使用O（41/δ）通过/圆形实现O（m·Nδlog2 n logm）的空间结合，而在多项式时间内实现O（41/δlogn）的近似因子（对于Δ= = = = = ω（1/logn）。使用O（M n）空间，确定性常数近似（即使给定指数时间）我们的算法可以应用于多方通信模型。
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.