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

Abstract

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$. We present two simplified and more intuitive analyses, for essentially the same algorithm, which also improve the space complexity to the optimal bound of $O(n\log n)$ bits --- this is optimal as the output matching requires $\Omega (n\log n)$ bits. Our analyses rely on a simple use of the primal-dual method and a simple accounting method.

Appears at the Symposium on Simplicity in Algorithms (SOSA) 2019