

























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(n\log^2 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(n\log n)$ bits --- this is optimal as the output matching requires $Ω(n\log n)$ bits. Our analyses rely on a simple use of the primal-dual method and a simple accounting method.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。