= Greedy two-approximation for maximum-weight matching
{title2=$w(M_{\mathrm{opt}})\leq2w(M_{\mathrm{greedy}})$}
For nonnegative weights on a finite <graph>, scan <edges> in nonincreasing weight order, selecting each when it shares no endpoint with an already selected <edge>. This <greedy matching> is a factor-two <approximation algorithm> for <maximum-weight matching>.
\b[Proof.] Charge each optimal <edge> to itself if selected, and otherwise to an earlier selected <edge> that blocked it. The receiving <edge> weighs at least as much. Each selected <edge> receives at most two charges, since its two endpoints each meet at most one optimal <edge>. Summing proves the bound. Sorting takes $O(|E|\log|E|)$ time, followed by a scan that records which <vertices> are used.
The factor is sharp even for strictly positive weights. On a four-<vertex> <path graph> with consecutive weights $1,1+\varepsilon,1$, where $0<\varepsilon<1$, the <greedy matching> weighs $1+\varepsilon$ and the optimal <matching in a graph> weighs two. Their ratio tends to two as $\varepsilon\downarrow0$. For infinitely many sizes, use $k$ disjoint copies with $\varepsilon=1/k$, $k\geq2$. This example isolates the obstruction: a locally attractive <edge> can block two compatible <edges>.
Back to article page
