One-dimensional Euclidean matching problem: Exact solutions, correlation functions, and universality

We discuss the equivalence relation between the Euclidean bipartite matching problem on the line and on the circumference and the Brownian bridge process on the same domains. The equivalence allows us to compute the correlation function and the optimal cost of the original combinatorial problem in the thermodynamic limit; moreover, we solve also the minimax problem on the line and on the circumference. The properties of the average cost and correlation functions are discussed.

Figure 1

Plot of $m\left(y_i\right)=\sqrt{N}(\frac{i}{N}-y_i)$ for a certain realization of the problem with $N=4096$.

Figure 2

Correlation function $\forall p>1$ in the OBC case for $N=1000$ obtained averaging over ${10}^4$ realizations (for clarity, not all data are represented).

Figure 3

Distribution density of the rescaled cost for different values of $p$ computed with $5\times {10}^5$ iterations and $N=5000$ for the OBC case.

Figure 4

Correlation function in the PBC case for $N=1000$ obtained averaging over ${10}^4$ realizations (for clarity, not all data are represented). The continuous line is the theoretical prediction for $p=2$; the dashed line corresponds to the $p\to \infty$ case.

Figure 5

Value of $c_p:=\overline{\langle m_p^2\left(t\right)\rangle }$ in the PBC case for $N=1000$ obtained from the fit of the correlation function, averaging over 5000 realizations, for different values of $p$.

Figure 6

Plot for the normalized map correlation function (32) obtained with ${10}^4$ iterations and $N=1000$ for the PBC case. The continuous line is the theoretical prediction for $p=2$, whilst the dotted line is obtained from the theoretical prediction for $p\to \infty$. The pole is at $\tau \left(p\right)=\frac{1}{2}-\frac{\sqrt{1-8c_p}}{2}$.

Figure 7

Density distribution of the rescaled cost for different values of $p$ computed with $2\times {10}^4$ iterations and $N=1000$ for the PBC case.