Deterministic $(1+\epsilon )$-Approximate Maximum Matching with $\mathsf{poly}(1/\epsilon )$ Passes in the Semi-Streaming Model and Beyond

Manuela Fischer, Slobodan Mitrović, Jara Uitto

We present a deterministic $(1+\epsilon )$-approximate maximum matching algorithm in $\mathsf{poly}1/\epsilon$ passes in the semi-streaming model, solving the long-standing o…