Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model
复制标题
DOI：
10.1137/100801901
复制
发表时间：
2009-07
期刊：
影响因子：
--
通讯作者：
L. Epstein;Asaf Levin;Julián Mestre;D. Segev
中科院分区：
文献类型：
--
作者：
L. Epstein;Asaf Levin;Julián Mestre;D. Segev
研究了半流模型下的最大权匹配问题，并对Zelke（Proc.\ STACS 2008，第669- 680页），通过设计一种确定性方法，其性能保证为$4.91 + \eps$。此外，我们研究{\em preemptive}在线算法，一个子类的一遍算法，我们只允许在内存中保持一个可行的匹配在任何时间点。所有已知的结果之前，泽尔克的属于这个子类。我们提供了一个下限为4.967 $的竞争力比任何这样的确定性算法，因此表明，未来的改进将不得不存储在内存中的一组边缘，这不一定是一个可行的匹配。最后，我们提出了一个实证研究，为了比较我们的方法，以前建议的算法的实际性能进行。
We study the maximum weight matching problem in the semi-streaming model, and improve on the currently best one-pass algorithm due to Zelke (Proc.\ STACS~'08, pages 669--680) by devising a deterministic approach whose performance guarantee is $4.91 + \eps$. In addition, we study {\em preemptive} online algorithms, a sub-class of one-pass algorithms where we are only allowed to maintain a feasible matching in memory at any point in time. All known results prior to Zelke's belong to this sub-class. We provide a lower bound of $4.967$ on the competitive ratio of any such deterministic algorithm, and hence show that future improvements will have to store in memory a set of edges which is not necessarily a feasible matching. We conclude by presenting an empirical study, conducted in order to compare the practical performance of our approach to that of previously suggested algorithms.