在圖中尋找大的或重的比對是一個普遍存在的組合優化問題。在本文中，我們設計了第一個非平凡的實作來近似動态權重比對問題。我們的第一個算法是基于随機漫步/路徑與動态規劃相結合。第二種算法由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