# Christofides algorithm

Jump to: navigation, search

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)/2w(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 e1,...,e2k be the (only) Eulerian path in $(O,B)$. Clearly both e1,e3,...,e2k-1 and e2,e4,...,e2k 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,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.