= Solution
The sharp <approximation algorithm> factor is \b[$c=2$]. Charge each <edge> $e$ of an optimal <maximum-weight matching> $M_o$ to an <edge> of the <greedy matching> $M_g$. If $e\in M_g$, charge it to itself. Otherwise it was rejected because a previously selected <edge> $g\in M_g$ shared an endpoint; charge $e$ to one such $g$. Since the scan is in nonincreasing weight order, $w(e)\leq w(g)$.
Each $g\in M_g$ receives at most two charges, since each of its two endpoints meets at most one <edge> of the <matching in a graph> $M_o$. If $g\in M_o$, only its own charge is possible. Thus
$$
\boxed{w(M_o)\leq2w(M_g).}
$$
This inequality also covers the edgeless <graph>, for which both weights are zero and the displayed ratio in the question is undefined.
For tightness, take a four-<vertex> <path graph> with weights $1,1+\varepsilon,1$ in order, where $0<\varepsilon<1$. The <greedy matching> chooses only the middle <edge>, of weight $1+\varepsilon$, whereas the optimal <matching in a graph> chooses both outer <edges>, of total weight $2$. Hence
$$
\frac{w(M_o)}{w(M_g)}=\frac{2}{1+\varepsilon}\longrightarrow2\qquad(\varepsilon\downarrow0).
$$
To obtain infinitely many different sizes, for each $k\geq2$ take $k$ disjoint copies with $\varepsilon=1/k$. Their weights add, so their ratio is $2/(1+1/k)\to2$. All weights are strictly positive, and the middle <edge> is uniquely heaviest in each copy. With all three weights equal to $1$, a permitted tie order selecting each middle <edge> first attains ratio $2$ exactly. The <greedy two-approximation for maximum-weight matching> is therefore best possible.
\Image[/past-exam-of-the-computer-science-course-of-the-university-of-oxford/2023/combinatorial-optimisation-greedy-matching.png]
{title=A uniquely heavier middle <edge> gives a <greedy matching> of weight $1+\varepsilon$, while the two outer <edges> give a <maximum-weight matching> of weight $2$}
Back to article page
