Data di Pubblicazione:
2019
Citazione:
Selberg integrals in 1D random Euclidean optimization problems / S. Caracciolo, A. Di Gioacchino, E.M. Malatesta, L.G. Molinari. - In: JOURNAL OF STATISTICAL MECHANICS: THEORY AND EXPERIMENT. - ISSN 1742-5468. - 2019:6(2019 Jun 06). [10.1088/1742-5468/ab11d7]
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 >> 1, 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.
Tipologia IRIS:
01 - Articolo su periodico
Keywords:
exact results, finite-size scaling, optimization over networks, random matrix theory and extensions
Elenco autori:
S. Caracciolo, A. Di Gioacchino, E.M. Malatesta, L.G. Molinari
Link alla scheda completa:
Link al Full Text: