Christofides' algorithm
/ kris-TOFF-ih-dees /
Christofides' algorithm is the famous improvement on the simple MST-doubling 2-approximation for metric TSP. Doubling every tree edge is wasteful — it pays double for the whole tree just to make every vertex have an even number of edges (which is what lets you trace one closed walk). Christofides' insight is that you do not need to double everything; you only need to fix up the vertices that are 'odd' in the tree, and you can do that far more cheaply with a clever matching. The payoff is a tighter 1.5-approximation, and for over four decades it remained the best ratio known for metric TSP.
The algorithm has three moves. First, build a minimum spanning tree T of the cities. Second, look at the vertices that have an odd number of edges in T — there is always an even count of such odd-degree vertices, a basic graph fact — and compute a minimum-weight perfect matching M among just those odd vertices, pairing them up as cheaply as possible. Add M's edges to T. Now every vertex has even degree, so the combined graph has an Eulerian circuit: a closed walk using every edge exactly once. Third, trace that circuit and shortcut past already-visited cities, exactly as in the MST method; the triangle inequality guarantees shortcutting never lengthens the result. Why 1.5? The tree costs MST <= OPT as before. The matching can be shown to cost at most OPT / 2: the odd vertices in optimal-tour order split into two alternating perfect matchings whose total is at most OPT, so the cheaper one — and hence the minimum matching — is at most OPT / 2. Adding them: tour <= MST + M <= OPT + OPT/2 = 1.5 * OPT.
Why it matters and the honest details. Christofides is the canonical 'a smarter lower-bound argument buys a better ratio' result, and it is genuinely used. The cost: computing a minimum-weight perfect matching is the expensive step, polynomial but markedly slower than building an MST, so the better ratio is not free. Two caveats: like the 2-approximation it requires the triangle inequality, and the 1.5 was only beaten very recently, by a tiny amount, and even that is far from the 1 we would love — metric TSP remains genuinely hard to approximate beyond a small constant.
Take five cities. Build the MST; suppose four of its vertices have odd degree. Christofides matches those four into two cheap pairs (minimum-weight perfect matching), adds those two edges, and now every vertex is even-degree. It walks the resulting Eulerian circuit, shortcutting repeats, to produce a tour guaranteed within 1.5x of optimal.
MST plus a cheap matching on odd-degree vertices, made Eulerian, then shortcut: 1.5 * OPT.
The matching is computed only among the odd-degree vertices of the MST, not all vertices, and it is a MINIMUM-weight perfect matching — that minimality is what delivers the OPT/2 bound. Skipping minimality or matching everyone would break the 1.5 guarantee.