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 A. Then, by invoking A 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 A: (1) In MPC and CONGEST, our framework invokes A for O(1/ε⁷ · log(1/ε)) times, substantially improving on O(1/ε³⁹) invocations following from [Fischer et al., STOC'22] and [Mitrovic et al., arXiv:2412.19057]. (2) In both online and offline fully dynamic settings, our framework yields an improvement in the dependence on $1/ε$ from exponential [Assadi et al., SODA25 and Liu, FOCS24] to polynomial.