2017/01/13 by Ghaffari, Mohsen, Wajc, David
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1701.03730
In a recent breakthrough, Paz and Schwartzman (SODA'17) presented a single-pass (2+ε)-approximation algorithm for the maximum weight matching problem in the semi-streaming model. Their algorithm uses O(nlog2 n) bits of space, for any constant ε>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(nlog n) bits --- this is optimal as the output matching requires Ω(nlog n) bits. Our analyses rely on a simple use of the primal-dual method and a simple accounting method.