2026-08-17T09:11:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9011 2024-03-06T10:43:08Z ddc:004 open_access

Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms Arar, Moab Chechik, Shiri Cohen, Sarel Stein, Cliff Wajc, David Dynamic Worst-case Maximum Matching Maximum Weight Matching We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic "approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic (2+epsilon)-approximate integral matching algorithm with small polylog worst-case update time. For the (2+epsilon)-approximation regime only a fractional fully-dynamic (2+epsilon)-matching algorithm with worst-case polylog update time was previously known, due to Bhattacharya et al. (SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio. As a consequence, we also obtain the first constant-approximate worst-case polylogarithmic update time maximum weight matching algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moab Arar and Shiri Chechik and Sarel Cohen and Cliff Stein and David Wajc 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.7 urn:nbn:de:0030-drops-90112 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.7 eng https://creativecommons.org/licenses/by/3.0/legalcode