313. Christofides
A -approximation algorithm for the metric TSP — produces tours guaranteed within optimal.
For 40 years, this was the best-known approximation ratio. In 2020, Karlin-Klein-Gharan improved it slightly (to ). Christofides’ algorithm remains the standard reference point.
313.1. The algorithm
Given a complete graph with distances satisfying the triangle inequality ():
- Build MST — minimum spanning tree of the graph
- Find odd-degree nodes in — call this set . (By handshake lemma, is even.)
- Min-weight perfect matching on — solve a matching problem on the subgraph induced by
- Combine MST + matching — gives a multigraph where every vertex has even degree
- Find Eulerian circuit on this multigraph — visits every edge exactly once
- 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 OPT.
313.2. Why ?
- MST cost: OPT (any TSP tour minus one edge is a spanning tree)
- Matching cost: OPT (a TSP tour on the odd-degree nodes can be decomposed into two perfect matchings; the cheaper is OPT)
- Total: MST + matching OPT OPT OPT
- Shortcutting only shortens — under triangle inequality, replacing with doesn’t increase length
313.3. Complexity
- MST: — see MST
- Min-weight matching: — most expensive step in practice
- Eulerian circuit:
- Total: , dominated by matching
The matching step makes Christofides slower than simpler heuristics like 2-opt on large instances.
313.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)
313.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