teeline · algorithms/christofides
Christofides — a ≤1.5× Approximation
The only simple TSP heuristic with a provable worst-case bound: the tour is always within 1.5× of optimal. Three ingredients — MST (skeleton, ≤ OPT),matching on the odd-degree vertices (patch, ≤ OPT/2), and anEulerian walk + shortcut (≤ MST + matching) — add up to the guarantee.
Pipeline
Approximation ratio
1.0× OPT1.5× bound
tour = 1.11× optimal
Why ≤ 1.5×?
MST 790 ≤ OPT 979
Match 296 ≤ OPT/2 490
Tour 1084 ≤ MST+matching 1086 ≤ 1.5·OPT 1469
Compare on this instance
Nearest neighbour
1.18×
Doubled MST (2×)
1.00×
Christofides
1.11×
MST edge matching edge final tour odd-degree vertex walker
MST — click Step to grow the tree (Prim's, cost 790)
phase
MST
MST cost
790
matching cost
296 (27%)
tour cost
1084
ratio
1.11×
step
0
Show
Speed
Scenarios