Past exam of the computer science course of the University of Oxford / 2023 / Combinatorial optimisation / 3 / c / ii / Solution

The sharp approximation algorithm factor is $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)\le 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. ThusThis 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+\epsilon ,1$ in order, where $0<\epsilon <1$. The greedy matching chooses only the middle edge, of weight $1+\epsilon$, whereas the optimal matching in a graph chooses both outer edges, of total weight $2$. HenceTo obtain infinitely many different sizes, for each $k\ge 2$ take $k$ disjoint copies with $\epsilon =1/k$. Their weights add, so their ratio is $2/(1+1/k)\to 2$. 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.