The number of optimal matchings for Euclidean Assignment on the line

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, $\sim \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\sim \frac{1}{2}N\log N+Ns+\mathcal{O}\left(\log N\right)$, where $s$ is a random variable whose distribution $p(s)$ does not depend on $N$. We give expressions for the asymptotics of 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

References in corpus (5)

• Singularity analysis, Hadamard products, and tree recurrences
• On the one dimensional Euclidean matching problem: exact solutions, correlation functions and universality
• Correlation function for the Grid-Poisson Euclidean matching on a line and on a circle
• Random Euclidean matching problems in one dimension
• On a solution to the Monge transport problem on the real line arising from the strictly concave case