We consider the Random Euclidean Assignment Problem in dimension d = 1, with linear cost function. In this version of the problem, in general, there is a large degeneracy of the ground state, i.e. there are many different optimal matchings (say, similar to exp( S-N) at size N). We characterize all possible optimal matchings of a given instance of the problem, and we give a simple product formula for their number. Then, we study the probability distribution of S-N (the zero-temperature entropy of the model), in the uniform random ensemble. We find that, for large N, S-N similar to 1/2 N log N + Ns + O (log N), where s is a random variable whose distribution p(s) does not depend on N. We give expressions for the moments of p(s), both from a formulation as a Brownian process, and via singularity analysis of the generating functions associated to S-N. The latter approach provides a combinatorial framework that allows to compute an asymptotic expansion to arbitrary order in 1/ N for the mean and the variance of S-N.

The Number of Optimal Matchings for Euclidean Assignment on the Line / S. Caracciolo, V. Erba, A. Sportiello. - In: JOURNAL OF STATISTICAL PHYSICS. - ISSN 0022-4715. - 183:1(2021 Apr), pp. 3.1-3.27. [10.1007/s10955-021-02741-1]

The Number of Optimal Matchings for Euclidean Assignment on the Line

S. Caracciolo
Primo
;
V. Erba
Secondo
;
2021

Abstract

We consider the Random Euclidean Assignment Problem in dimension d = 1, with linear cost function. In this version of the problem, in general, there is a large degeneracy of the ground state, i.e. there are many different optimal matchings (say, similar to exp( S-N) at size N). We characterize all possible optimal matchings of a given instance of the problem, and we give a simple product formula for their number. Then, we study the probability distribution of S-N (the zero-temperature entropy of the model), in the uniform random ensemble. We find that, for large N, S-N similar to 1/2 N log N + Ns + O (log N), where s is a random variable whose distribution p(s) does not depend on N. We give expressions for the moments of p(s), both from a formulation as a Brownian process, and via singularity analysis of the generating functions associated to S-N. The latter approach provides a combinatorial framework that allows to compute an asymptotic expansion to arbitrary order in 1/ N for the mean and the variance of S-N.
random combinatorial optimization; Euclidean correlations; assignment problem;
Settore FIS/02 - Fisica Teorica, Modelli e Metodi Matematici
21-mar-2021
Article (author)
File in questo prodotto:
File Dimensione Formato  
2101.04926-2.pdf

accesso aperto

Tipologia: Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione 596.67 kB
Formato Adobe PDF
596.67 kB Adobe PDF Visualizza/Apri
Caracciolo2021_Article_TheNumberOfOptimalMatchingsFor.pdf

accesso aperto

Tipologia: Publisher's version/PDF
Dimensione 917.41 kB
Formato Adobe PDF
917.41 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2434/826601
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact