2025/03/03 by Slobodan Mitrović, Mitrović, Slobodan, Wen-Horng Sheu +1 · 2 citations
Computer Science · #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Stochastic Gradient Optimization Techniques
paper · pdf · doi:10.48550/arxiv.2503.01147
openalex publication_date 2025/03/03 · openalex created_date 2025/10/12 · openalex updated_date 2026/07/28
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/ε7 ⋅ log(1/ε)) times, substantially improving on O(1/ε39) 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.