2021/06/08 by Manuela Fischer, Fischer, Manuela, Slobodan Mitrović +3 · 4 citations
Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2106.04179
openalex publication_date 2021/06/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We present a deterministic (1+ε)-approximate maximum matching algorithm in poly 1/ε passes in the semi-streaming model, solving the long-standing open problem of breaking the exponential barrier in the dependence on 1/ε. Our algorithm exponentially improves on the well-known randomized (1/ε)O(1/ε)-pass algorithm from the seminal work by McGregor~[APPROX05], the recent deterministic algorithm by Tirodkar with the same pass complexity~[FSTTCS18]. Up to polynomial factors in 1/ε, our work matches the state-of-the-art deterministic (log n / log log n) ⋅ (1/ε)-pass algorithm by Ahn and Guha~[TOPC18], that is allowed a dependence on the number of nodes n. Our result also makes progress on the Open Problem 60 at sublinear.info. Moreover, we design a general framework that simulates our approach for the streaming setting in other models of computation. This framework requires access to an algorithm computing an O(1)-approximate maximum matching and an algorithm for processing disjoint (poly 1 / ε)-size connected components. Instantiating our framework in CONGEST yields a poly(logn, 1/ε) round algorithm for computing (1+ε)-approximate maximum matching. In terms of the dependence on 1/ε, this result improves exponentially state-of-the-art result by Lotker, Patt-Shamir, and Pettie~[LPSP15]. Our framework leads to the same quality of improvement in the context of the Massively Parallel Computation model as well.