Loading…

Average optimal cost for the Euclidean TSP in one dimension

The traveling salesman problem is one of the most studied combinatorial optimization problems, because of the simplicity of its statement and the difficulty in its solution. We study the traveling salesman problem when the positions of the cities are chosen at random in the unit interval and the cos...

Full description

Saved in:
Bibliographic Details
Published in:Journal of physics. A, Mathematical and theoretical Mathematical and theoretical, 2019-06, Vol.52 (26), p.264003
Main Authors: Caracciolo, Sergio, Di Gioacchino, Andrea, Malatesta, Enrico M, Vanoni, Carlo
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The traveling salesman problem is one of the most studied combinatorial optimization problems, because of the simplicity of its statement and the difficulty in its solution. We study the traveling salesman problem when the positions of the cities are chosen at random in the unit interval and the cost associated with the travel between two cities is their distance elevated to an arbitrary power . We characterize the optimal cycle and compute the average optimal cost for every number of cities when the measure used to choose the position of the cities is flat and asymptotically for large number of cities in the other cases. We also show that the optimal cost is a self-averaging quantity, and we test our analytical results with extensive simulations.
ISSN:1751-8113
1751-8121
DOI:10.1088/1751-8121/ab1600