Towards Tight Bounds for the Streaming Set Cover Problem
Towards Tight Bounds for the Streaming Set Cover Problem
复制标题
流媒体集覆盖问题的严格界限
DOI：
10.1145/2902251.2902287
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Vakilian
中科院分区：
文献类型：
--
作者：
P. Indyk;S. Mahabadi;A. Vakilian
我们考虑了数据流模型中的经典集合覆盖问题。对于n个元素和m个集合（m ≥ n），我们给出了一个具有强次线性~O（mnδ）空间和对数逼近因子的O（1/δ）-遍算法.这比Demaine等人的早期算法有了显著的改进。[10]使用了指数级更大的通道数。我们补充这一结果表明，我们的算法所表现出的通道和空间的数量之间的权衡是紧密的，至少当近似因子等于1。具体地说，我们证明了任何精确使用（{1 over 2δ}-1）遍计算集合覆盖的算法必须在m=O（n）的范围内使用~Ω（mnδ）空间。此外，我们考虑的问题中的几何设置，其中元素是点在R2和集是圆盘，轴平行的矩形，或脂肪三角形在平面上，并表明我们的算法（略有修改）使用最佳~O（n）空间找到一个对数逼近O（1/δ）遍。最后，我们证明了任何区分大小为2和3的覆盖的随机一遍算法必须使用线性（即，Ω（mn））空间量。这是第一个结果表明，一个随机的，近似算法不能实现一个空间界是次线性的输入大小。这表明，使用多个通道可能是必要的，以便实现该问题的次线性空间边界，同时保证小的近似因子。
We consider the classic Set Cover problem in the data stream model. For n elements and m sets (m ≥ n) we give a O(1/δ)-pass algorithm with a strongly sub-linear ~O(mnδ) space and logarithmic approximation factor. This yields a significant improvement over the earlier algorithm of Demaine et al. [10] that uses exponentially larger number of passes. We complement this result by showing that the tradeoff between the number of passes and space exhibited by our algorithm is tight, at least when the approximation factor is equal to 1. Specifically, we show that any algorithm that computes set cover exactly using ({1 over 2δ}-1) passes must use ~Ω(mnδ) space in the regime of m=O(n). Furthermore, we consider the problem in the geometric setting where the elements are points in R2 and sets are either discs, axis-parallel rectangles, or fat triangles in the plane, and show that our algorithm (with a slight modification) uses the optimal ~O(n) space to find a logarithmic approximation in O(1/δ) passes. Finally, we show that any randomized one-pass algorithm that distinguishes between covers of size 2 and 3 must use a linear (i.e., Ω(mn)) amount of space. This is the first result showing that a randomized, approximate algorithm cannot achieve a space bound that is sublinear in the input size. This indicates that using multiple passes might be necessary in order to achieve sub-linear space bounds for this problem while guaranteeing small approximation factors.