Planar Euclidean maximum traveling salesman problem
Given a finite set of points in the plane, the maximum traveling salesman problem asks for a tour through all the points whose total Euclidean length is as large as possible.
Barvinok gave a polynomial-time approximation scheme. Barvinok, Johnson, Woeginger and Woodroofe solved the problem exactly for polyhedral norms in fixed dimension, in time $O(n^{f-2}\log n)$ when the unit ball has $f$ facets. Fekete showed that it takes $O(n)$ time for rectilinear distances in the plane but is NP-hard for Euclidean distances in three dimensions and on the sphere, and conjectured that the planar Euclidean case is NP-hard. The problem is not known to be in NP: a polynomial-time algorithm would need some handle on comparing sums of square roots.
Problem. For a finite point set in the plane, is computing a longest Euclidean tour NP-hard, or can it be done in polynomial time?
Source: Origin uncertain; earliest known mention Barvinok (1996), who gave a PTAS; see Fekete (1999) and Barvinok, Fekete, Johnson, Tamir, Woeginger and Woodroofe (2003); Problem 49 of The Open Problems Project (Demaine, Mitchell and O'Rourke).
Imported from topp.openproblem.net.
Classification
- Primary
- MG — Metric Geometry
- Secondary
- CO, OC
- Keywords
- Euclidean distances, maximum traveling salesman problem, The Open Problems Project
References
@article{barvinok1996,
author = {Barvinok, Alexander I.},
title = {Two Algorithmic Results for the {TSP}},
journal = {Math. Oper. Res.},
volume = {21},
year = {1996},
pages = {65--84}
}
@inproceedings{barvinok1998,
author = {Barvinok, Alexander and Johnson, David S. and Woeginger, Gerhard J. and Woodroofe, Russell},
title = {The maximum traveling salesman problem under polyhedral norms},
booktitle = {Sixth Conference on Integer Programming and Combinatorial Optimization (IPCO '98)},
series = {Springer LNCS},
volume = {1412},
year = {1998},
pages = {195--201}
}
@inproceedings{fekete1999,
author = {Fekete, S. P.},
title = {Simplicity and hardness of the Maximum Traveling Salesman Problem under geometric distances},
booktitle = {Proc. 10th ACM-SIAM Sympos. Discrete Algorithms (SODA '99)},
year = {1999},
pages = {337--345}
}
@article{barvinok2003,
author = {Barvinok, A. and Fekete, S. P. and Johnson, D. S. and Tamir, A. and Woeginger, G. J. and Woodroofe, R.},
title = {The geometric maximum {T}raveling {S}alesman problem},
journal = {Journal of the ACM},
volume = {50},
number = {5},
year = {2003},
pages = {641--664}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01093, "Planar Euclidean maximum traveling salesman problem", clopen.solutions.