Almost Optimal Streaming Algorithms for Coverage Problems
Almost Optimal Streaming Algorithms for Coverage Problems
复制标题
覆盖问题的近乎最优流算法
DOI：
10.1145/3087556.3087585
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
V. Mirrokni
中科院分区：
文献类型：
--
作者：
M. Bateni;Hossein Esfandiari;V. Mirrokni
最大的覆盖范围和最小设置覆盖问题 - - 在流媒体模型中广泛研究了覆盖范围的问题。关于Oracle访问集合的明确或隐式假设，忽略了在本文中一次读取和存储整个集合的复杂性，我们解决了上述缺点，并以改进的近似因素和改善的空间复杂性来介绍算法此外，与以前的大多数工作不同，结果几乎是在更一般的边缘模型中。从任意顺序的设置到元素（表示成员资格）独立于集合的尺寸或元素的地面集的大小。为了实现上述结果，我们引入了一种新的一般素描技术，以实现覆盖范围的功能：一个人可以将此素描方案应用于覆盖算法，以将覆盖范围问题转换为（1-ε）α-approximation Algorithm流媒体模型中的问题。最终，在集合的任何亚家族上发挥作用，我们表明我们的流算法达到了几乎最佳的空间复杂性。
Maximum coverage and minimum set cover problems---here collectively called coverage problems---have been studied extensively in streaming models. However, previous research not only achieves suboptimal approximation factors and space complexities but also study a restricted set-arrival model which makes an explicit or implicit assumption on oracle access to the sets, ignoring the complexity of reading and storing the whole set at once. In this paper, we address the above shortcomings and present algorithms with improved approximation factor and improved space complexity, and prove that our results are almost tight. Moreover, unlike most of the previous work, our results hold in a more general edge-arrival model. More specifically, consider an instance with n sets, together covering m elements. Information arrives in the form of "edges" from sets to elements (denoting membership) in arbitrary order. We present (almost) optimal approximation algorithms for maximum coverage and minimum set cover problems in the streaming model with an (almost) optimal space complexity of Õ(n); i.e., the space is independent of the size of the sets or the size of the ground set of elements. These results not only improve the best known algorithms for the set-arrival model, but also are the first such algorithms for the more powerful edge-arrival model. In order to achieve the above results, we introduce a new general sketching technique for coverage functions: One can apply this sketching scheme to convert an α-approximation algorithm for a coverage problem to a (1-ε)α-approximation algorithm for the same problem in streaming model. We show the significance of our sketching technique by ruling out the possibility of solving coverage problems via accessing (as a black box) a (1 ± ε)-approximate oracle (e.g., a sketch function) that estimates the coverage function on any subfamily of the sets. Finally, we show that our streaming algorithms achieve an almost optimal space complexity.
用于估计平面图及其他区域中的匹配大小的流算法
DOI：
10.1145/3230819
发表时间：
2015
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Hossein Esfandiari;Mohammad Taghi Hajiaghayi;Vahid Liaghat;Morteza Monemizadeh;Krzysztof Onak
通讯作者：
Krzysztof Onak
DOI：
10.1137/1.9781611974331.ch92
发表时间：
2016-01
期刊：
--
影响因子：
--
作者：
R. Chitnis;Graham Cormode;Hossein Esfandiari;M. Hajiaghayi;A. Mcgregor;M. Monemizadeh;Sofya Vorotnikova
通讯作者：
R. Chitnis;Graham Cormode;Hossein Esfandiari;M. Hajiaghayi;A. Mcgregor;M. Monemizadeh;Sofya Vorotnikova