A framework for boosting matching approximation: parallel, distributed, and dynamic
Slobodan Mitrović, Wen-Horng Sheu · 2025
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 Ā: