A $(2+ϵ)$-Approximation for Maximum Weight Matching in the Semi-Streaming Model

We present a simple deterministic single-pass $(2+ϵ)$-approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves upon the currently best known approximation ratio of $(4+ϵ)$. Our algorithm uses $O(n{\log }^{2}n)$ bits of space for constant values of $ϵ$. It relies on a variation of the local-ratio theorem, which may be of use for other algorithms in the semi-streaming model as well.