Article ID: | iaor20012052 |
Country: | United States |
Volume: | 29 |
Issue: | 3 |
Start Page Number: | 697 |
End Page Number: | 711 |
Publication Date: | Jan 2000 |
Journal: | SIAM Journal On Computing |
Authors: | Coppersmith Don, Aggarwal Alok, Schieber Baruch, Motwani Rajeev, Khanna Sanjeev |
Motivated by applications in robotics, we formulate the problem of minimizing the total angle cost of a TSP tour for a set of points in Euclidean space, where the angle cost of a tour is the sum of the direction changes at the points. We establish the NP-hardness of both this problem and its relaxation to the cycle cover problem. We then consider the issue of designing approximation algorithms for these problems and show that both problems can be approximated to within a ratio of