HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

Fully-dynamic Weighted Matching Approximation in Practice

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

https://hal.inria.fr/hal-03210915
Contributor : Bora Uçar Connect in order to contact the contributor
Submitted on : Wednesday, April 28, 2021 - 11:36:59 AM
Last modification on : Monday, May 16, 2022 - 4:46:02 PM
Long-term archiving on: : Thursday, July 29, 2021 - 6:34:19 PM

File

paper.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Eugenio Angriman, Henning Meyerhenke, Christian Schulz, Bora Uçar. Fully-dynamic Weighted Matching Approximation in Practice. ACDA 2021 - SIAM Conference on Applied and Computational Discrete Algorithms, SIAM, Jul 2021, Virtual, France. ⟨10.1137/1.9781611976830.4⟩. ⟨hal-03210915⟩

Share

Metrics

Record views

50

Files downloads

91