EuroCG 2017

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

Fekete and Krupke

Front image

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.

Download: Paper, Slides

This paper is based on chapter 5 of my master’s thesis Algorithmic methods for complex dynamic sweeping problems. Please check there for further material.

Errata

Mosquito drone and corresponding images by Aaron Becker and his team in Houston.