Selberg integrals in 1D random Euclidean optimization problems

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 , the points are chosen at random with uniform measure. We derive the exact average cost for the rand...

Full description

Saved in:
Bibliographic Details
Published in:Journal of statistical mechanics 2019-06, Vol.2019 (6), p.63401
Main Authors: Caracciolo, Sergio, Di Gioacchino, Andrea, Malatesta, Enrico M, Molinari, Luca G
Format: Article
Language:English
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: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 , the points are chosen at random with uniform measure. We derive the exact average cost for the random assignment problem, for any number of points using Selberg's integrals. Some variants of these integrals enable the exact average cost for the bipartite travelling salesman problem to be derived.
ISSN:1742-5468
1742-5468
DOI:10.1088/1742-5468/ab11d7