Theorem 10.13 (Christofides): the tour returned by Christofides' heuristic satisfies
ProvedSupplyChainTheory.christofides_boundTheorem 10.13. For every instance of the TSP that satisfies the triangle inequality,
where is the length of the optimal tour and the length of the tour returned by Christofides' heuristic (Algorithm 10.6): find a minimum spanning tree , find a minimum-weight perfect matching on the odd-degree nodes of , take an Eulerian tour of the graph formed by the edges of and of (an edge may appear in both), and shortcut it by visiting the nodes in order of first appearance.
The book's proof: by Lemma 10.9; the optimal tour restricted to the odd nodes by shortcutting has length at most and splits into two perfect matchings on those nodes, so ; the Eulerian tour has length , and shortcutting does not lengthen it. This is the best worst-case bound known for the metric TSP; Problem 10.13 shows it is tight, and Lemma 10.18 records that it holds even against the LP relaxation.
Formalization Note The graph is a multigraph when a matching edge repeats a tree edge, so it is represented by its Eulerian walk: a closed walk in the complete graph whose edge multiset is the sum of the tree's and the matching's. Every MST, minimum matching, Eulerian tour and start node is covered.
import Definitions.Def_SupplyChainTheory_tsp
open Classical
namespace SupplyChainTheory
theorem christofides_bound {n : ℕ} (c : Fin n → Fin n → ℝ) (hc : IsMetric c) (hn : 1 ≤ n)
(T : SimpleGraph (Fin n)) (hT : IsMST c T) (M : Finset (Sym2 (Fin n)))
(hM : IsMinMatchingOn c (oddNodes T) M) (v : Fin n) (W : (⊤ : SimpleGraph (Fin n)).Walk v v)
(hW : (W.edges : Multiset (Sym2 (Fin n))) = T.edgeFinset.val + M.val)
(τ : Equiv.Perm (Fin n)) (hτ : IsShortcut W.support τ) :
tourLength c τ ≤ (3 / 2 : ℝ) * optTourLength c := by sorry
end SupplyChainTheory
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.
Confirmed by the moderator at approval.