The Library
Deterministic dynamic matching in worst-case update time
Tools
Kiss, Peter (2022) Deterministic dynamic matching in worst-case update time. In: Innovations in Theoretical Computer Science 2022, Berkley, CA, USA, 31 Jan - 03 Feb 2022. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 215 94:1-94:21. doi:10.4230/LIPIcs.ITCS.2022.94 ISSN 1868-8969.
|
PDF
WRAP-Deterministic-dynamic-matching-in-worst-case-update-time-Kiss-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (840Kb) | Preview |
|
PDF
WRAP-Deterministic-dynamic-matching-worst-case-update-time-2021.pdf - Publisher's Proof Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (841Kb) |
||
PDF
WRAP-Deterministic-dynamic-matching-worst-case-update-time-2021.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (569Kb) |
Official URL: http://doi.org/10.4230/LIPIcs.ITCS.2022.94
Abstract
We present deterministic algorithms for maintaining a (3/2+ϵ) and (2+ϵ)-approximate maximum matching in a fully dynamic graph with worst-case update times O^(n−−√) and O~(1) respectively. The fastest known deterministic worst-case update time algorithms for achieving approximation ratio (2−δ) (for any δ>0) and (2+ϵ) were both shown by Roghani et al. [2021] with update times O(n3/4) and Oϵ(n−−√) respectively. We close the gap between worst-case and amortized algorithms for the two approximation ratios as the best deterministic amortized update times for the problem are Oϵ(n−−√) and O~(1) which were shown in Bernstein and Stein [SODA'2021] and Bhattacharya and Kiss [ICALP'2021] respectively.
In order to achieve both results we explicitly state a method implicitly used in Nanongkai and Saranurak [STOC'2017] and Bernstein et al. [arXiv'2020] which allows to transform dynamic algorithms capable of processing the input in batches to a dynamic algorithms with worst-case update time.
\textbf{Independent Work:} Independently and concurrently to our work Grandoni et al. [arXiv'2021] has presented a fully dynamic algorithm for maintaining a (3/2+ϵ)-approximate maximum matching with deterministic worst-case update time Oϵ(n−−√).
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Library of Congress Subject Headings (LCSH): | Computer algorithms , Computer programming , Machine theory, Integer programming, Random variables | ||||||
Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 25 January 2022 | ||||||
Dates: |
|
||||||
Volume: | 215 | ||||||
Page Range: | 94:1-94:21 | ||||||
Article Number: | 94 | ||||||
DOI: | 10.4230/LIPIcs.ITCS.2022.94 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 23 November 2021 | ||||||
Date of first compliant Open Access: | 24 November 2021 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | Innovations in Theoretical Computer Science 2022 | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Berkley, CA, USA | ||||||
Date(s) of Event: | 31 Jan - 03 Feb 2022 | ||||||
Related URLs: | |||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year