Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
Sublinear Estimation of Weighted Matchings in Dynamic Data Streams
复制标题
动态数据流中加权匹配的次线性估计
DOI：
10.1007/978-3-662-48350-3_23
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Chris Schwiegelshohn
中科院分区：
文献类型：
--
作者：
Marc Bury;Chris Schwiegelshohn
本文提出了一种通过扩充任何无权重匹配规模的估计程序来估计最大权重匹配权重的算法。该算法可在包括动态图流在内的任何流模型中实现。我们还首次针对平面图（或任何有界树度的图）在动态图流中给出了最大匹配规模的常数估计，使用了\(\tilde{O}(n^{4/5})\)空间，这也扩展到了加权匹配。利用卡普拉洛夫、坎纳和苏丹（2014年）之前的结果，我们分别在随机顺序流中使用多对数\((n)\)空间获得了一般图的多对数\((n)\)近似。此外，对于任何在对抗流中估计最大匹配规模至多达到\(1 + O(\epsilon)\)因子的随机算法，我们给出了\(\Omega(n^{1 - \epsilon})\)的空间下界。
This paper presents an algorithm for estimating the weight of a maximum weighted matching by augmenting any estimation routine for the size of an unweighted matching. The algorithm is implementable in any streaming model including dynamic graph streams. We also give the first constant estimation for the maximum matching size in a dynamic graph stream for planar graphs (or any graph with bounded arboricity) using \(\tilde{O}(n^{4/5})\) space which also extends to weighted matching. Using previous results by Kapralov, Khanna, and Sudan (2014) we obtain a polylog(n) approximation for general graphs using polylog(n) space in random order streams, respectively. In addition, we give a space lower bound of Ω(n1 − e) for any randomized algorithm estimating the size of a maximum matching up to a 1 + O(e) factor for adversarial streams.
用于估计平面图及其他区域中的匹配大小的流算法
DOI：
10.1145/3230819
发表时间：
2015
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Hossein Esfandiari;Mohammad Taghi Hajiaghayi;Vahid Liaghat;Morteza Monemizadeh;Krzysztof Onak
通讯作者：
Krzysztof Onak