License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.7
URN: urn:nbn:de:0030-drops-90112
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9011/
Arar, Moab ;
Chechik, Shiri ;
Cohen, Sarel ;
Stein, Cliff ;
Wajc, David
Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms
Abstract
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.
BibTeX - Entry
@InProceedings{arar_et_al:LIPIcs:2018:9011,
author = {Moab Arar and Shiri Chechik and Sarel Cohen and Cliff Stein and David Wajc},
title = {{Dynamic Matching: Reducing Integral Algorithms to Approximately-Maximal Fractional Algorithms}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {7:1--7:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-076-7},
ISSN = {1868-8969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9011},
URN = {urn:nbn:de:0030-drops-90112},
doi = {10.4230/LIPIcs.ICALP.2018.7},
annote = {Keywords: Dynamic, Worst-case, Maximum Matching, Maximum Weight Matching}
}
Keywords: |
|
Dynamic, Worst-case, Maximum Matching, Maximum Weight Matching |
Collection: |
|
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) |
Issue Date: |
|
2018 |
Date of publication: |
|
04.07.2018 |