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:

Create a minimum spanning tree $T$ of $G$ .
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$ .
Combine the edges of $M$ and $T$ to form a multigraph $H$ .
Form an Eulerian circuit in $H$ (H is Eulerian because it is connected, with only even-degree vertices).
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) \geq 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) \geq w(B)$ . We show that there is a perfect matching of vertices from $O$ with weight under $w(B)/2 \leq 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 1,..., e 2k$ be the (only) Eulerian path in $(O,B)$ . Clearly both $e 1, e 3,..., e 2k-1$ and $e 2, e 4,..., 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) \leq 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,E\right)$ 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 ( $T\cup M$ ).
	Calculate Euler tour on $T\cup 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 algorithms 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.