Christofides Algorithm

Purpose: A $\frac{3}{2}$-approximation for metric TSP (symmetric costs satisfying the triangle inequality), in polynomial time. It stood as the best known ratio from 1976 until a $\frac{3}{2}-\epsilon$ result in 2020.

Algorithm

1. Build a minimum spanning tree $T$ of the complete metric graph.
2. Let $O$ be the set of vertices with odd degree in $T$. (By the handshake lemma, $|O|$ is even.)
3. Find a minimum-weight perfect matching $M$ on the induced subgraph over $O$ — this is the expensive step, $O(n^3)$ via Blossom.
4. Form the multigraph $T\cup M$. Every vertex now has even degree, so an Eulerian circuit exists; find it with Hierholzer.
5. Shortcut the Eulerian circuit: walk it and skip already-visited vertices. The triangle inequality guarantees shortcutting never increases the cost.

Complexity

• Time: $O(n^3)$, dominated by the minimum-weight perfect matching
• Space: $O(n^2)$

Proof of the 3/2 Ratio

Let $\mathrm{OPT}$ be the optimal tour cost.

(a) $w(T)\le \mathrm{OPT}$. Deleting any edge from the optimal tour leaves a spanning path, which is a spanning tree; the MST is no heavier.

(b) $w(M)\le \frac{1}{2}\mathrm{OPT}$. Take the optimal tour and shortcut it to visit only the vertices of $O$, in the order they appear. By the triangle inequality this cycle costs at most $\mathrm{OPT}$. A cycle on an even number of vertices decomposes into two disjoint perfect matchings; the cheaper of the two costs at most $\frac{1}{2}\mathrm{OPT}$, and the minimum matching is no heavier still.

(c) The Euler tour costs $w(T)+w(M)\le \frac{3}{2}\mathrm{OPT}$, and shortcutting only helps. ∎

Why the triangle inequality is essential

Without it, TSP has no constant-factor polynomial approximation unless P = NP: a $c$-approximation would let you decide Hamiltonian cycle by setting non-edges to a huge weight. The metric restriction is what makes any guarantee possible.

Comparison

Method	Ratio	Time
Nearest neighbour	$\Theta (\log n)$	$O(n^2)$
Double the MST (“double tree”)	$2$	$O(n^2)$
Christofides	$3/2$	$O(n^3)$
Karlin-Klein-Oveis Gharan (2020)	$3/2-10^{-36}$	polynomial
Held-Karp	exact	$O(2^n{n}^2)$
2-opt / Lin-Kernighan local search	no guarantee	fast, excellent in practice

In practice

For real instances, nobody runs Christofides. A cheap construction plus 2-opt / Or-opt / Lin-Kernighan local search gets within 1-2% of optimal far faster. Christofides matters because of the guarantee, not the output quality.

Variants / Use Cases

• Double-tree algorithm — skip the matching, just double every MST edge; ratio 2 but $O(n^2)$ and trivial to write
• Travelling Salesman — the problem page
• Simulated annealing / local search — what you actually submit when $n$ is large and the checker is a score
• Approximation Algorithms — the general theory of ratios and hardness