A (2 + ϵ)-approximation for maximum weight matching in the semi-streaming model
Ami Paz, Gregory Schwartzman · arXiv (Cornell University) · 2017
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 (3.5 + ϵ).Our algorithm uses O(n log2n) space for constant values of ϵ. It relies on a variation of the local-ratio theorem, which may be of independent interest in the semi-streaming model.