Christofides algorithm

From Wikipedia, the free encyclopedia

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 $<var>A</var>$ denote the edge set of the optimal solution of TSP for $<var>G</var>$ . Because $<var>(V,A)</var>$ is connected, it contains some spanning tree $<var>T</var>$ and thus $<var>w(A)</var> \geq <var>w(T)</var>$ . 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 $<var>w(A)</var> \geq <var>w(B)</var>$ . We show that there is a perfect matching of vertices from $O$ with weight under $<var>w(B)/2</var> \leq <var>w(A)/2</var>$ 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 $<var>e</var> 1,...,<var>e</var> 2k$ be the (only) Eulerian path in $(O,B)$ . Clearly both $<var>e</var> 1,<var>e</var> 3,...,<var>e</var> 2k-1$ and $<var>e</var> 2,<var>e</var> 4,...,<var>e</var> 2k$ are perfect matchings and the weight of at least one of them is less than or equal to $<var>w(B)/2</var>$ . Thus $<var>w(M)+w(T)</var> \leq <var>w(A) + w(A)/2</var>$ 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.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.