Faster Semi-streaming Matchings via Alternating Trees

Slobodan Mitrović, Anish Mukherjee, Piotr Sankowski +1

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