Deterministic (1+ε)-approximate maximum matching with poly(1/ε) passes in the semi-streaming model and beyond

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 (logn / loglogn) · (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.