Christofides algorithm

From Wikipedia, the free encyclopedia
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[edit]

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[edit]

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[edit]

Metrischer Graph mit 5 Knoten.svg Given: metric graph G=\left(V,E\right) with edge weights
Christofides MST.svg Calculate minimum spanning tree T.
V'.svg Calculate the set of vertices V' with odd degree in T.
G V'.svg Reduce G to the vertices of V' (G|_{V'}).
Christofides Matching.svg Calculate matching M with minimum weight in G|_{V'}.
TuM.svg Unite matching and spanning tree (T\cup M).
Eulertour.svg Calculate Euler tour on T\cup M (A-B-C-A-D-E-A).
Eulertour bereinigt.svg 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[edit]

  • 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.