next up previous contents index CD CD Algorithms
Next: Exercises Up: Approximation Algorithms Previous: Approximating Vertex Cover

The Euclidean Traveling Salesman


In most natural applications of the traveling salesman problem, direct routes are inherently shorter than indirect routes. For example, if the edge weights of the graph are ``as the crow flies'', straight-line distances between pairs of cities, the shortest path from x to y will always be to fly directly.      

Figure: The triangle inequality typically holds in geometric and weighted graph problems.  

The edge weights induced by Euclidean geometry satisfy the triangle inequality, which insists that tex2html_wrap_inline26342 for all triples of vertices u, v, and w. The reasonableness of this condition is shown in Figure gif. Note that the cost of airfares is an example of a distance function that violates the triangle inequality, since it is sometimes cheaper to fly through an intermediate city than to fly to the destination directly. TSP remains hard when the distances are Euclidean distances in the plane.

Whenever a graph obeys the triangle inequality, we can approximate the optimal traveling salesman tour using minimum spanning trees. First, observe that the weight of a minimum spanning tree is a lower bound on the cost of the optimal tour. Why? Deleting any edge from a tour leaves a path, the total weight of which must be no greater than that of the original tour. This path has no cycles, and hence is a tree, which means its weight is at least that of the minimum spanning tree. Thus the minimum spanning tree cost gives a lower bound on the optimal tour.  

Consider now what happens in performing a depth-first traversal of a spanning tree. Suppose we walk through each tree edge as we process it in a depth-first search. We will visit each edge twice, once going down the tree when exploring it and once going up after exploring the entire subtree. For example, in the depth-first search of Figure gif, we visit the vertices in order 1-2-1-3-5-8-5-9-5-3-6-3-1-4-7-10-7-11-7-4-1, thus using every tree edge exactly twice. Therefore, this tour has weight twice that of the minimum spanning tree, and hence at most twice optimal.  

Figure: A depth-first traversal of a spanning tree, with the shortcut tour  

However, vertices will be repeated on this depth-first search tour. To remove the extra vertices, at each step we can take a shortest path to the next unvisited vertex. The shortcut tour for the tree above is 1-2-3-5-8-9-6-4-7-10-11-1. Because we have replaced a chain of edges by a single direct edge, the triangle inequality ensures that the tour can only get shorter. Thus the shortcut tour is within weight twice that of optimal. More complicated but better approximation algorithms for Euclidean TSP are mentioned in Section gif. No approximation algorithms exist for TSPs that do not satisfy the triangle inequality.  

next up previous contents index CD CD Algorithms
Next: Exercises Up: Approximation Algorithms Previous: Approximating Vertex Cover

Mon Jun 2 23:33:50 EDT 1997