Faster Semi-streaming Matchings via Alternating Trees

Slobodan Mitrović, Anish Mukherjee, Piotr Sankowski +1

We design a deterministic algorithm for the $(1+\hat{I}\mu )$-approximate maximum matching problem. Our primary result demonstrates that this problem can be solved in $O(\hat{I}{\mu }^{-6})$ semi-stre…