Fully dynamic approximate maximum matching and minimum vertex cover in O(log3 n) worst case update time
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 5869
- Type
- E - Conference contribution
- DOI
-
10.1137/1.9781611974782.30
- Title of conference / published proceedings
- Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
- First page
- 470
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- -
- Year of publication
- 2017
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
T - Theory and Foundations
- Citation count
- 18
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Published at the flagship conference on algorithms. Considers a fundamental optimization problem (Chapter 1 of the standard "Approximation Algorithms" textbook by Vazirani) under dynamically changing inputs, and presents an algorithm for maintaining a near-optimal solution. The first result in the literature on dynamic algorithms for general graphs to attain the "holy grail" of simultaneously being deterministic and having polylogarithmic worst-case update time. This algorithm has been crucially used in subsequent papers to obtain improved bounds for dynamic matching, e.g., by Arar, Chechik, Cohen (Tel Aviv University), Stein (Columbia) and Wajc (Carnegie Mellon University) in ICALP'18, and by Wajc in STOC'20.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
