Approximation Algorithms for the Minimum Bends Traveling Salesman Problem (Extended Abstract)

摘要

) Cliff Stein # David P. Wagner # Dartmouth College Computer Science Technical Report TR2000-367 May 9, 2000 Abstract The problem of traversing a set of points in the order that minimizes the total distance traveled (traveling salesman problem) is one of the most famous and well-studied problems in combinatorial optimization. It has many applications, and has been a testbed for many of the must useful ideas in algorithm design and analysis. The usual metric, minimizing the total distance traveled, is an important one, but many other metrics are of interest. In this paper, we introduce the metric of minimizing the number of turns in the tour, given that the input points are in the Euclidean plane. To our knowledge this metric has not been studied previously. It is motivated by applications in robotics and in the movement of other heavy machinery: for many such devices turning is an expensive operation. We give approximation algorithms for several variants of the traveling...