= Christofides algorithm
{c}
{title2=$\operatorname{ALG}\leq\tfrac32\operatorname{OPT}$}
Compute a <minimum spanning tree>, then a <minimum-weight perfect matching> on its odd-degree vertices. Their multiset union is connected with even degrees, so it has an <Euler circuit>. Shortcut repeated vertices to obtain a metric tour. The tree costs at most the optimal tour, and shortcutting the optimal tour to its odd-degree subset gives a cyclic order whose alternating matchings show that the added matching costs at most half the optimum. The result is a polynomial-time $3/2$-<approximation algorithm> for symmetric metric instances.
Back to article page
