Random Euclidean matching problems in one dimension

We discuss the optimal matching solution for both the assignment problem and the matching problem in one dimension for a large class of convex cost functions. We consider the problem in a compact set with the topology both of the interval and of the circumference. Afterwards, we assume the points' positions to be random variables identically and independently distributed on the considered domain. We analytically obtain the average optimal cost in the asymptotic regime of very large number of points $N$ and some correlation functions for a power-law-type cost function in the form $c\left(z\right)=z^p$, both in the $p>1$ case and in the $p<0$ case. The scaling of the optimal mean cost with the number of points is $N^{-p/2}$ for the assignment and $N^{-p}$ for the matching when $p>1$, whereas in both cases it is a constant when $p<0$. Finally, our predictions are compared with the results of numerical simulations.

Figure 1

Correlation functions $c_p\left(r\right)$ (inset) and ${\widehat{c}}_p\left(r\right)$ for the assignment problem on the interval $\mathrm{\Lambda }$ with $p<0$, as defined in Eqs. (73) and (76), respectively. Observe that a finite-size effect appears for $r\to 0$ in the numerical data for ${\widehat{c}}_p\left(r\right)$. In all cases, the theoretical predictions are represented in solid line.

Figure 2

Numerical results for the assignment problem. Error bars are typically smaller than the markers in the figures. (a) Numerical results for the average optimal cost (inset) and its finite-size corrections in the assignment problem with $p>1$ on $\mathrm{\Lambda }$. We fitted the obtained numerical results using the fitting function $f\left(N\right)=a+b/N$ for each value of $p,a$ and $b$ being fitting parameters corresponding to the leading cost and to the finite-size corrections, respectively. We present our numerical results and we compare them with our prediction given in Eq. (56). (b) Numerical results for the average optimal cost in the assignment problem on $\mathrm{\Lambda }$ with $p<0$. The theoretical predictions are given in Eq. (71) and they are represented in solid lines. In the upper inset, numerical results for $\overline{{\tau }^2}$ for different values of $p$, obtained using two-parameters fitting function in the form $f\left(N\right)=\alpha +\beta /N,\alpha$ being the numerical estimation for $\overline{{\tau }^2}$. We compare them with the prediction in Eq. (67). (c) Numerical results for the average optimal cost (inset) and its finite-size corrections in the assignment problem with $p>1$ on the circumference. We fitted the numerical results obtained for different values of $N$ at fixed $p$ using the fitting function in the form given in Eq. (82). See also Table 1. (d) Numerical results for the average optimal cost and its finite-size corrections in the assignment problem with $p<0$ on the circumference. We present our numerical results and we compare them with our theoretical predictions for the asymptotic behavior given in Eq. (85) (solid lines).

Figure 3

Numerical results for the matching problem. Error bars are typically smaller than the markers in the figures. (a) Numerical results for the finite-size corrections to the average optimal cost (inset) in the matching problem with $p>1$ on $\mathrm{\Lambda }$. We compare our numerical results with our numerical prediction given in Eq. (92) (solid lines). (b) Numerical results for average optimal cost in the matching problem on $\mathrm{\Lambda }$ with $p<0$. The theoretical predictions (solid lines), for any value of $N>-p$, are given by Eq. (101). Observe that for $N\gg 1$ $2^p{\varepsilon }_N^{\left(p\right)}$ is linear in $N^{-1}$ (inset). (c) Numerical results for average optimal cost in the matching problem on the circumference with $p>1$. The theoretical predictions (solid lines) for the asymptotic behavior are given by Eq. (113). Observe that for $N\gg 1$ the corrections to the asymptotic cost scale as $1/\sqrt{N}$ (inset). (d) Numerical results for average optimal cost in the matching problem on the circumference with $p<0$. The theoretical predictions (solid lines) are given by Eq. (115) and they are correct for all values of $N>-p$, as expected. Observe that for $N\gg 1$ $2^p{\varepsilon }_N^{\left(p\right)}$ is linear in $1/\sqrt{N}$ (inset).