New deterministic approximation algorithms for fully dynamic matching
- Submitting institution
-
The University of Warwick
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- 5870
- Type
- E - Conference contribution
- DOI
-
10.1145/2897518.2897568
- Title of conference / published proceedings
- 48th Annual ACM Symposium on Theory of Computing
- First page
- 398
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- June
- Year of publication
- 2016
- 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
- 20
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- Published in one of the two top conferences in theoretical computer science. Gives the first application of deterministic rounding of linear programs - a ubiquitous technique in approximation algorithms (see, e.g., the Williamson and Shmoys textbook) - in a dynamic setting where the input changes over time. This leads to the first efficient, deterministic dynamic algorithm for a textbook optimization problem. The paper has two main results. Stubbs and Vassilevska Williams (Stanford) extend one of these results to weighted graphs. Wajc (CMU) builds on top of the other result to give an improved algorithm for dynamic matching in bipartite graphs.
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -