Christofides algorithm

From Wikipedia, the free encyclopedia

The goal of the Christofides heuristics algorithm is to find a near-optimal solution to the instances of the traveling salesman problem that satisfy the triangle equality. 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.

Pseudo-code:
Step 1: Create the minimum spanning tree MST (V,T) of G.
Step 2: Denote O the set of vertices with odd degree in (V,T) and find a perfect matching1 M with minimal weight in the complete graph over the vertices from O.
Step 3: Combine the edges of M and T to make a multigraph H=(V,M\cup T).
Step 4: Find an Euler path in H by skipping vertices already seen.

1: Perfect matching vertices: A subset of edges without common vertices, of a connected graph that touches all vertices exactly once.

[edit] Cost of algorithm

It can be proven that the algorithm's solution has a length within the factor of 3/2 of the optimum. Indeed:

Denote A the edge set of the optimal solution of TSP for G. Since (V,A) is connected, it contains some spanning tree and thus w(A)\ge w(T). Further denote B the edge set of the optimal solution of TSP for the complete graph over vertices from O. It follows that w(A)\ge w(B). We show that there is a perfect matching of vertices from O with weight under w(B)/2\le w(A)/2 and therefore we have the same upper bound for M (since M is the minimal perfect matching). Since O must contain an even number of vertices, a perfect matching exists. Let us denote e_1,\ldots,e_{2k} the (only) Eulerian path in (O,B). Clearly both \{e_1,e_3,\ldots,e_{2k-1}\} and \{e_2,e_4,\ldots,e_{2k}\} are perfect matchings and the weight of at least one of them is under w(B) / 2. Thus w(M)+w(T)\le w(A)+w(A)/2 and from the triangle inequality follows that the above algorithm is 3/2-approximative.


[edit] References

Languages