A framework for boosting matching approximation: parallel, distributed, and dynamic
This work designs a framework for boosting the approximation guarantee of maximum matching algorithms. As input, the framework receives a parameter ϵ > 0 and an oracle access to a Θ(1)-approximate maximum matching algorithm Ā. Then, by invoking Ā for poly(1/ϵ) many times, the framework outputs a 1 + ϵ approximation of a maximum matching. Our approach yields several improvements in terms of the number of invocations to Ā:
Authors
- Wen-Horng Sheu (ORCID: https://orcid.org/0000-0002-2707-8612)
- Slobodan Mitrović
Institutions
- University of Novi Sad (RS)
- University of California, Davis (US)
Publication Details
- Published
- 2025-07-16
- DOI
- https://doi.org/10.1145/3694906.3743312
- Citations
- 1
- Primary Topic
- Complexity and Algorithms in Graphs
- Type
- article
- Field-Weighted Citation Impact
- 1.50
Funders
- National Science Foundation
- Simons Institute for the Theory of Computing, University of California Berkeley