在图中寻找大的或重的匹配是一个普遍存在的组合优化问题。在本文中，我们设计了第一个非平凡的实现来近似动态加权匹配问题。我们的第一个算法是基于随机漫步/路径与动态规划相结合。第二种算法由Stubbs和Williams提出，但没有实现。粗略地说，他们的算法使用动态非加权匹配算法作为一个子程序(在多层方法中);这允许我们使用以前的动态非加权匹配算法作为一个黑盒，以获得一个全动态加权匹配算法。我们在大量的动态实例上对这些算法进行了实证研究，并与最优加权匹配算法进行了比较。我们的实验表明，随机游走算法通常比Stubbs/Williams(关于时间/质量的权衡)好得多，其结果往往离最优不远。
原文题目：Fully-dynamic Weighted Matching Approximation in Practice
原文：Finding large or heavy matchings in graphs is a ubiquitous combinatorial optimization problem. In this paper, we engineer the first non-trivial implementations for approximating the dynamic weighted matching problem. Our first algorithm is based on random walks/paths combined with dynamic programming. The second algorithm has been introduced by Stubbs and Williams without an implementation. Roughly speaking, their algorithm uses dynamic unweighted matching algorithms as a subroutine (within a multilevel approach); this allows us to use previous work on dynamic unweighted matching algorithms as a black box in order to obtain a fully-dynamic weighted matching algorithm. We empirically study the algorithms on an extensive set of dynamic instances and compare them with optimal weighted matchings. Our experiments show that the random walk algorithm typically fares much better than Stubbs/Williams (regarding the time/quality tradeoff), and its results are often not far from the optimum.
实践中的全动态加权匹配逼近.pdf