Average optimal cost for the Euclidean TSP in one dimension

Abstract

The traveling-salesman problem is one of the most studied combinatorial optimization problems, because of the simplicity in 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 to the travel between two cities is their distance elevated to an arbitrary power $p\in \mathbb{R}$. 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.

arXiv comment14 pages, 8 figures

References in corpus (13)

• Scaling hypothesis for the Euclidean bipartite matching problem
• Scaling hypothesis for the Euclidean bipartite matching problem II. Correlation functions
• The random link approximation for the Euclidean traveling salesman problem
• Comparing Mean Field and Euclidean Matching Problems
• On the one dimensional Euclidean matching problem: exact solutions, correlation functions and universality
• On the finite size corrections to some random matching problems
• Quadratic stochastic Euclidean bipartite matching problem
• Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle
• Random Euclidean matching problems in one dimension
• Solution for a bipartite Euclidean traveling-salesman problem in one dimension
• Finite-size corrections in the random assignment problem
• Exact value for the average optimal cost of bipartite traveling-salesman and 2-factor problems in two dimensions
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension

Cited by in corpus (1)

• Selberg integrals in 1D random Euclidean optimization problems