# EuroCG 2017

## Covering Tours with Turn Cost: Variants, Approximation and Practical Solution

Fekete and Krupke

Abstract: For a given set P of points in the plane, the Angular-Metric Traveling Salesman Problem (AM-TSP) asks for a tour on P that minimizes the total turn along the tour. While there exists a PTAS for the Euclidean TSP, for the AM-TSP only a O(log n) approximation algorithm is known. We introduce a number of generalizations and provide approximation algorithms whose performance depend on the angular resolution. We also develop exact methods for computing provably optimal solutions, and present an array of experimental results.

• The runtime dependency is polynomial and not as written linear on $\omega$.