Next: Problem 50: Pointed Spanning Trees in Triangulations
Previous: Problem 48: Bounded-Degree Minimum Euclidean Spanning Tree
What is the complexity of finding a tour of maximum Euclidean length for a planar point set?
[Bar96] showed that there is a PTAS for the problem. No earlier mention is known.
Open.
How does the complexity of a natural problem depend on the geometry of distances?
[BJrW98] showed that a maximum length tour can be found in polynomial time for polyhedral metrics in spaces of finite dimension, i.e., for metrics for which the unit ball is a convex body with f facets. The resulting complexity is O(n^{f-2}\log n).
[Fek99] showed that the maximum TSP can be solved in time O(n) for rectilinear distances in the plane, but is NP-hard for Euclidean distances in three-dimensional space, or on the surface of a sphere. Conjectures the case of planar Euclidean distances to be NP-hard.
More recent details and related problems can be found in [BFJ+03].
The problem is not even known to be in NP. A polynomial algorithm would require some understanding of problem 33 (sum of square roots), at least for classes of instances arising from the computation of tour length.
Also related is the Planar Euclidean maximum scatter TSP: What is the complexity of finding a tour for a planar point set in \Re^d, such that the Euclidean length of the shortest edge is maximized? Stated in [ACM+97], shown NP-hard in dimensions d\geq 3 in [Fek99], open for d=2. Also, no bounds on approximation are known in a geometric context; the best known aproximation algorithm from [ACM+97] achieves an approximation factor of 2, but does not use geometry.
traveling salesman; optimization; point sets
S.P. Fekete, 1 Aug. 2003.
Esther M. Arkin, Y.-J. Chiang, Joseph S. B. Mitchell, Steven S. Skiena, and T. Yang. On the maximum scatter TSP. In Proc. 8th ACM-SIAM Sympos. Discrete Algorithms, pages 211–220, 1997.
A. Barvinok, S. P. Fekete, D. S. Johnson, A. Tamir, G. J. Woeginger, and R. Wodroofe. The geometric maximum Traveling Salesman problem. Journal of the ACM, 50:641–664, 2003.
Alexander I. Barvinok. Two algorithmic results for the TSP. Math. Oper. Res., 21:65–84, 1996.
Alexander Barvinok, David S. Johnson, Gerhard J. Woeginge r, and Russell Woodroofe. The maximum traveling salesman problem under polyhedral norms. In Sixth Conference on Integer Programming and Combinatorial Optim ization, volume 1412 of Springer LNCS, pages 195–201, June 1998.
Sándor P. Fekete. Simplicity and hardness of the maximum traveling salesman problem under geometric distances. Manuscript (submitted), Mathematisches Institut, Universität zu Köln, 1998.
S. P. Fekete. Simplicity and hardness of the maximum traveling salesman probl em under geometric distances. In Proc. 10th ACM-SIAM Sympos. Discrete Algorithms, pages 337–345, 1999.