Christofides algorithm

The goal of the Christofides heuristic algorithm (named after Nicos Christofides) is to find a solution to the instances of the traveling salesman problem where the edge weights satisfy the triangle inequality. Let G = (V,w) be an instance of TSP, i.e. G is a complete graph on the set V of vertices with weight function w assigning a nonnegative real weight to every edge of G.

Pseudo-code:
Step 1: Create the minimum spanning tree MST T of G.
Step 2: Let O be the set of vertices with odd degree in T and find a perfect matching M with minimum weight in the complete graph over the vertices from O.
Step 3: Combine the edges of M and T to form a multigraph H.
Step 4: Form an Eulerian circuit in H (H is Eulerian because it is connected, with only even-degree vertices).
Step 5: Make the circuit found in previous step Hamiltonian by skipping visited nodes (shortcutting).

Approximation ratio

The cost of the solution produced by the algorithm is within 3/2 of the optimum.

The proof is as follows:

Let A denote the edge set of the optimal solution of TSP for G. Because (V,A) is connected, it contains some spanning tree T and thus w(A) ≥ w(T). Further let B denote the edge set of the optimal solution of TSP for the complete graph over vertices from O. Because the edge weights are triangular (so visiting more nodes cannot reduce total cost), we know that w(A) ≥ w(B). We show that there is a perfect matching of vertices from O with weight under w(A)/2 ≤ w(B)/2 and therefore we have the same upper bound for M (because M is a perfect matching of minimum cost). Because O must contain an even number of vertices, a perfect matching exists. Let e₁,...,e_2k be the (only) Eulerian path in (O,B). Clearly both e₁,e₃,...,e_2k-1 and e₂,e₄,...,e_2k are perfect matchings and the weight of at least one of them is less than or equal to w(B)/2. Thus w(M)+w(T) ≤ w(A) + w(A)/2 and from the triangle inequality it follows that the algorithm is 3/2-approximative.

References

• NIST Christofides Algorithm Definition
• Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.