Christofides algorithm

The Christofides heuristic is an algorithm used for the approximation of metric traveling salesman problems. He was for a long time, the best approximation for Euclidean graphs. ( Arora / 1996 Mitchell presented a better PTAS ago. )

Formally, the procedure is similar as for the minimum - spanning-tree heuristic:

Quality guarantee

It can be shown that the Christofides heuristic is a 1.5 - approximation. This means that the resulting tour is at most by half longer than the optimal tour. The proof is based on a repeated application of the triangle inequality.

• The minimum spanning tree ( MST) is anyway less than or equal to the optimal solution, since any solution of the Traveling Salesman Problem (TSP ) contains a spanning tree.
• Regarding the Matching the following applies: Be the sequence of nodes formerly of odd degree in the optimum solution; in between there are any other nodes. Consider the two matchings as well. Then, due to the triangle inequality that So is the total cost of the optimal solution greater than or equal those of any two matchings, in particular, therefore twice the minimum matching. Then a minimal matching is only at most half as large as the optimal solution.

Example

This tour is the output of the algorithm.