Approximation algorithms for the minimum bends traveling salesman problem. (English) Zbl 1010.90519

Aardal, Karen (ed.) et al., Integer programming and combinatorial optimization. 8th international IPCO conference, Utrecht, Netherlands, June 13-15, 2001. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 2081, 406-421 (2001).
Summary: 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. 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. We give approximation algorithms for several variants under this metric. For the general case we give a logarithmic approximation algorithm. For the case when the lines of the tour are restricted to being either horizontal or vertical, we give a 2-approximation algorithm. If we have the further restriction that no two points are allowed to have the same x- or y-coordinate, we give an algorithm that finds a tour which makes at most two turns more than the optimal tour. We also introduce several interesting algorithmic techniques for decomposing sets of points in the Euclidean plane that we believe to be of independent interest.
For the entire collection see [Zbl 0967.00091].


90C35 Programming involving graphs or networks
68W25 Approximation algorithms
Full Text: Link