Space-Optimal Semi-Streaming for (2+ε)-Approximate Matching.
Mohsen Ghaffari · arXiv (Cornell University) · 2017
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. Their algorithm uses $O(n\log^2 n)$ bits of space, for any constant $\epsilon>0$. In this note, we present a different analysis, for essentially the same algorithm, that improves the space complexity to the optimal bound of $O(n\log n)$ bits, while also providing a more intuitive explanation of the process.