Tight bounds for single-pass streaming complexity of the set cover problem
Tight bounds for single-pass streaming complexity of the set cover problem
复制标题
集合覆盖问题的单遍流复杂性的严格界限
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Yang Li
中科院分区：
文献类型：
--
作者：
Sepehr Assadi;S. Khanna;Yang Li
我们解决了空间复杂性的单通道流算法近似经典的集合覆盖问题。为了通过单遍流算法找到α-近似集合覆盖（对于α= o（n）），我们证明了Θ（mn/α）空间是充分和必要的（直到O（logn）因子）;这里m表示集合的数量，n表示宇宙的大小。这为Indyk（2015）提出的关于使用次线性空间的小近似因子的单遍算法的可能性的开放问题提供了一个强有力的否定答案。我们进一步研究了估计最小集合覆盖的大小的问题（而不是寻找实际的集合），并建立了在这种情况下可以实现的额外的空间节省因子α，并且这是最好的可能。换句话说，我们证明了Θ（mn/α2）空间对于估计最小集合覆盖的大小在α的因子内是充分和必要的（直到对数因子）。我们的算法实际上适用于估计覆盖整数规划的最优值的更一般的问题。另一方面，我们的下界甚至对于集合以随机顺序呈现的集合覆盖实例也成立。
We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an α-approximate set cover (for α= o(√n)) via a single-pass streaming algorithm, we show that Θ(mn/α) space is both sufficient and necessary (up to an O(logn) factor); here m denotes number of the sets and n denotes size of the universe. This provides a strong negative answer to the open question posed by Indyk (2015) regarding the possibility of having a single-pass algorithm with a small approximation factor that uses sub-linear space. We further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets), and establish that an additional factor of α saving in the space is achievable in this case and that this is the best possible. In other words, we show that Θ(mn/α2) space is both sufficient and necessary (up to logarithmic factors) for estimating the size of a minimum set cover to within a factor of α. Our algorithm in fact works for the more general problem of estimating the optimal value of a covering integer program. On the other hand, our lower bound holds even for set cover instances where the sets are presented in a random order.