316. Christofides

A $\frac{3}{2}$-approximation algorithm for the metric TSP — produces tours guaranteed within $1.5\times$ optimal.

For 40 years, this was the best-known approximation ratio. In 2020, Karlin-Klein-Gharan improved it slightly (to $1.5-{10}^{-36}$). Christofides’ algorithm remains the standard reference point.

316.1. The algorithm

Given a complete graph with distances satisfying the triangle inequality (${𝑐}_{𝑖𝑘}\le {𝑐}_{𝑖𝑗}+{𝑐}_{𝑗𝑘}$):

1. Build MST — minimum spanning tree $𝑇$ of the graph
2. Find odd-degree nodes in $𝑇$ — call this set $𝑂$. (By handshake lemma, $|𝑂|$ is even.)
3. Min-weight perfect matching on $𝑂$ — solve a matching problem on the subgraph induced by $𝑂$
4. Combine MST + matching — gives a multigraph where every vertex has even degree
5. Find Eulerian circuit on this multigraph — visits every edge exactly once
6. Shortcut — convert the Eulerian circuit to a TSP tour by skipping repeated visits (uses triangle inequality)

The output is a Hamiltonian tour with total length $\le 1.5\cdot$ OPT.

316.2. Why $\frac{3}{2}$?

• MST cost: $\le$ OPT (any TSP tour minus one edge is a spanning tree)
• Matching cost: $\le \frac{1}{2}$ OPT (a TSP tour on the odd-degree nodes can be decomposed into two perfect matchings; the cheaper is $\le \frac{1}{2}$ OPT)
• Total: MST + matching $\le$ OPT $+\frac{1}{2}$ OPT $=1.5$ OPT
• Shortcutting only shortens — under triangle inequality, replacing $𝐴\to 𝐵\to 𝐶$ with $𝐴\to 𝐶$ doesn’t increase length

316.3. Complexity

• MST: $𝑂\left(𝐸log𝑉\right)$ — see MST
• Min-weight matching: $𝑂\left(|𝑂{|}^3\right)$ — most expensive step in practice
• Eulerian circuit: $𝑂\left(𝐸\right)$
• Total: $𝑂\left({𝑉}^3\right)$, dominated by matching

The matching step makes Christofides slower than simpler heuristics like 2-opt on large instances.

316.4. When triangle inequality fails

If the graph doesn’t satisfy triangle inequality (e.g., asymmetric TSP with arbitrary costs):

• No constant-factor approximation exists unless P = NP
• Christofides doesn’t apply

For Euclidean TSP in the plane:

• Better approximations exist (PTAS by Arora 1998)
• Christofides is rarely the best practical choice (LKH-3 is usually better)

316.5. Worth knowing in 2026

• 2-opt / LK heuristics give better solutions in practice (no guarantee but tighter results)
• Christofides is the theoretical benchmark — used in proofs, complexity arguments
• Metric TSP: still the only easy worst-case bound to cite

316.6. See also

• TSP — problem
• TSP 2-opt — heuristic alternative
• MST — used in step 1