Streaming Weighted Matchings: Optimal Meets Greedy
Streaming Weighted Matchings: Optimal Meets Greedy
复制标题
流式加权匹配：最优与贪婪的结合
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Samson Zhou
中科院分区：
文献类型：
--
作者：
Elena Grigorescu;M. Monemizadeh;Samson Zhou
我们考虑了近似最大加权匹配的问题，当基础加权图$ g（v，e）$的边缘以流方式揭示。我们分析了以前最著名的$（4+epsilon）$ - 近似算法的变体，这是由于Crouch和Stubbs（大约，2014年），并证明他们的猜想是其达到3.5+Epsilon $的紧密近似值。
该算法将流分解为子流中，并在其上运行贪婪的最大匹配算法。在流的末尾，将选定的边缘作为输入给出最佳最大加权匹配算法。为了分析近似保证，我们开发了一个新颖的充电论点，在该论点中，我们将$ g $的最大加权匹配的边缘分解为几个天然类别，然后将它们分别充电到我们算法的匹配输出边缘。
We consider the problem of approximating a maximum weighted matching, when the edges of an underlying weighted graph $G(V,E)$ are revealed in a streaming fashion. We analyze a variant of the previously best-known $(4+epsilon)$-approximation algorithm due to Crouch and Stubbs (APPROX, 2014), and prove their conjecture that it achieves a tight approximation factor of $3.5+epsilon$.
The algorithm splits the stream into substreams on which it runs a greedy maximum matching algorithm. At the end of the stream, the selected edges are given as input to an optimal maximum weighted matching algorithm. To analyze the approximation guarantee, we develop a novel charging argument in which we decompose the edges of a maximum weighted matching of $G$ into a few natural classes, and then charge them separately to the edges of the matching output by our algorithm.
用于估计平面图及其他区域中的匹配大小的流算法
DOI：
10.1145/3230819
发表时间：
2015
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
Hossein Esfandiari;Mohammad Taghi Hajiaghayi;Vahid Liaghat;Morteza Monemizadeh;Krzysztof Onak
通讯作者：
Krzysztof Onak