Selberg integrals in 1D random Euclidean optimization problems

Abstract

We consider a set of Euclidean optimization problems in one dimension, where the cost function associated to the couple of points $x$ and $y$ is the Euclidean distance between them to an arbitrary power $p\ge 1$, and the points are chosen at random with flat measure. We derive the exact average cost for the random assignment problem, for any number of points, by using Selberg's integrals. Some variants of these integrals allows to derive also the exact average cost for the bipartite travelling salesman problem.

arXiv comment9 pages, 2 figures

References in corpus (13)

• Spectra of Euclidean Random Matrices
• Continuum limit of total variation on point clouds
• Scaling hypothesis for the Euclidean bipartite matching problem
• Scaling hypothesis for the Euclidean bipartite matching problem II. Correlation functions
• 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
• Solution for a bipartite Euclidean traveling-salesman problem in one dimension
• Exact value for the average optimal cost of bipartite traveling-salesman and 2-factor problems in two dimensions
• Intertwining Operators for a Degenerate Double Affine Hecke Algebra and Multivariable Orthogonal Polynomials
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension
• Average optimal cost for the Euclidean TSP in one dimension

Cited by in corpus (3)

• Euclidean random matching in 2D for non-constant densities
• The Dyck bound in the concave 1-dimensional random assignment model
• The number of optimal matchings for Euclidean Assignment on the line