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

Abstract

We present a simple deterministic single-pass $(2+\epsilon )$-approximation algorithm for the maximum weight matching problem in the semi-streaming model. This improves upon the currently best known approximation ratio of $(4+\epsilon )$. Our algorithm uses $O(n{\log }^{2}n)$ bits of space for constant values of $\epsilon$. 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.

References in corpus (2)

• On Estimating Maximum Matching Size in Graph Streams
• Sublinear Estimation of Weighted Matchings in Dynamic Data Streams

Cited by in corpus (1)

• Semi-Streaming Matching in a Single Pass I: A New Framework for Lower Bounds via Blueprints