Christofides Metric Tour Parity Certificate
Repair a tree’s odd degrees, shortcut an Euler tour and verify a metric route approximation bound.
Free theory articleRepair a tree’s odd degrees, shortcut an Euler tour and verify a metric route approximation bound.
Concept & interpretation
The Christofides algorithm is a heuristic that provides a 1.5-approximation for the Metric Traveling Salesperson Problem (TSP).
experiment
You can interactively explore the algorithm on different metric point sets.
- Select the Point fixture to
Asymmetric6. - Set the Start vertex to
2. - Observe the MST, the identified odd vertices, the perfect matching, and the final shortcut tour cost.
- Verify that the
Tour Costis certified to be within 1.5 times theExact Optimum.