| HAL-Inria | Publications, software ... of Inria's scientists |
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.
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
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)