Approximation Algorithms for the Minimum Bends Traveling Salesman Problem
作者： Clifford Stein , David P. Wagner*
关键词: Christofides algorithm 、 Combinatorics 、 Approximation algorithm 、 Lin–Kernighan heuristic 、 Travelling salesman problem 、 Nearest neighbour algorithm 、 Computer science 、 2-opt 、 Bottleneck traveling salesman problem 、 Combinatorial optimization
摘要: The problem of traversing a set points in the order that minimizes total distance traveled (traveling salesman problem) is one most famous and well-studied problems combinatorial optimization. In this paper, we introduce metric minimizing number turns tour, given input are Euclidean plane. We give approximation algorithms for several variants under metric. For general case logarithmic algorithm. when lines tour restricted to being either horizontal or vertical, 2-approximation If have further restriction no two allowed same x- y-coordinate, an algorithm finds which makes at more than optimal tour. also interesting algorithmic techniques decomposing sets plane believe be independent interest.
springer.com
sci-hub.st 参考文章(28)
Foto Afrati, Stavros Cosmadakis, Christos H. Papadimitriou, George Papageorgiou, Nadia Papakostantinou, The complexity of the travelling repairman problem RAIRO - Theoretical Informatics and Applications. ,vol. 20, pp. 79- 87 ,(1986) , 10.1051/ITA/1986200100791
Alexander Barvinok, David S. Johnson, Gerhard J. Woeginger, Russell Woodroofe, The Maximum Traveling Salesman Problem Under Polyhedral Norms integer programming and combinatorial optimization. pp. 195- 201 ,(1998) , 10.1007/3-540-69346-7_15
Esther M. Arkin, Steven Skiena, Joseph S. B. Mitchell, Yi-Jen Chiang, Tae-Cheon Yang, On the Maximum Scatter TSP (Extended Abstract). symposium on discrete algorithms. pp. 211- 220 ,(1997)
Avrim Blum, Prasad Chalasani, Don Coppersmith, Bill Pulleyblank, Prabhakar Raghavan, Madhu Sudan, The minimum latency problem Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94. pp. 163- 171 ,(1994) , 10.1145/195058.195125
Rong-chii Duh, Martin Fürer, Approximation of k-set cover by semi-local optimization symposium on the theory of computing. pp. 256- 264 ,(1997) , 10.1145/258533.258599
Esther M. Arkin, Saurabh Sethia, Erik D. Demaine, Sándor P. Fekete, Joseph S. B. Mitchell, Michael A. Bender, Optimal covering tours with turn costs symposium on discrete algorithms. pp. 138- 147 ,(2001) , 10.5555/365411.365430
Joseph S. B. Mitchell, Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k -MST, and Related Problems SIAM Journal on Computing. ,vol. 28, pp. 1298- 1309 ,(1999) , 10.1137/S0097539796309764
H. Brönnimann, M. T. Goodrich, Almost optimal set covers in finite VC-dimension Discrete and Computational Geometry. ,vol. 14, pp. 463- 479 ,(1995) , 10.1007/BF02570718
Nimrod Megiddo, Arie Tamir, On the complexity of locating linear facilities in the plane Operations Research Letters. ,vol. 1, pp. 194- 197 ,(1982) , 10.1016/0167-6377(82)90039-6
Refael Hassin, Shlomi Rubinstein, Better approximations for max TSP Information Processing Letters. ,vol. 75, pp. 181- 186 ,(2000) , 10.1016/S0020-0190(00)00097-1