Simplified and Space-Optimal Semi-Streaming for $(2+\epsilon )$-Approximate Matching

Mohsen Ghaffari, David Wajc

In a recent breakthrough, Paz and Schwartzman (SODA'17) presented a single-pass ($2+\epsilon$)-approximation algorithm for the maximum weight matching problem in the semi-streaming model.…