Solution for a bipartite Euclidean traveling-salesman problem 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 characterize the optimal cycle for every convex and increasing cost function when the points are thrown independently and with an identical probability distribution in a compact interval. We compute the average optimal cost for every number of points when the distance function is the square of the Euclidean distance. We also show that the average optimal cost is not a self-averaging quantity by explicitly computing the variance of its distribution in the thermodynamic limit. Moreover, we prove that the cost of the optimal cycle is not smaller than twice the cost of the optimal assignment of the same set of points. Interestingly, this bound is saturated in the thermodynamic limit.

arXiv comment9 pages, 5 figures

References in corpus (9)

• Scaling hypothesis for the Euclidean bipartite matching problem
• Scaling hypothesis for the Euclidean bipartite matching problem II. Correlation functions
• Comparing Mean Field and Euclidean Matching Problems
• The random link approximation for the Euclidean traveling salesman problem
• On the one dimensional Euclidean matching problem: exact solutions, correlation functions and universality
• 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
• One-loop diagrams in the Random Euclidean Matching Problem

Cited by in corpus (6)

• Statistical learning theory of structured data
• Exact value for the average optimal cost of bipartite traveling-salesman and 2-factor problems in two dimensions
• Anomalous scaling of the optimal cost in the one-dimensional random assignment problem
• Selberg integrals in 1D random Euclidean optimization problems
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension
• Average optimal cost for the Euclidean TSP in one dimension