Christofides algorithm

The goal of the Christofides approximation 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$.

Algorithm

In pseudo-code:

1. Create a minimum spanning tree $T$ of $G$.
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$.
3. Combine the edges of $M$ and $T$ to form a multigraph $H$.
4. Form an Eulerian circuit in $H$ (H is Eulerian because it is connected, with only even-degree vertices).
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(B)/2 ≤ w(A)/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.

Example

	Given: metric graph $G=left(V,Eright)$ with edge weights
	Calculate minimum spanning tree $T$.
	Calculate the set of vertices $V'$ with odd degree in $T$.
	Reduce $G$ to the vertices of $V'$ ($G|_{V'}$).
	Calculate matching $M$ with minimum weight in $G|_{V'}$.
	Unite matching and spanning tree ($Tcup M$).
	Calculate Euler tour on $Tcup M$ (A-B-C-A-D-E-A).
	Remove reoccuring vertices and replace by direct connections (A-B-C-D-E-A). In metric graphs, this step can not lengthen the tour. This tour is the algorithm's output.

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.