Finite-size corrections in the random assignment problem

We analytically derive, in the context of the replica formalism, the first finite-size corrections to the average optimal cost in the random assignment problem for a quite generic distribution law for the costs. We show that, when moving from a power-law distribution to a $\mathrm{\Gamma }$ distribution, the leading correction changes both in sign and in its scaling properties. We also examine the behavior of the corrections when approaching a $\delta$-function distribution. By using a numerical solution of the saddle-point equations, we provide predictions that are confirmed by numerical simulations.

Figure 1

Numerical results for ${\widehat{E}}_1^{\text{P}}\left(N\right)$ and ${\widehat{E}}_1^{\mathrm{\Gamma }}\left(N\right)$ for several values of $N$. Note that finite-size corrections have a different sign for $N\to +\infty$. We have represented also the theoretical predictions for both cases obtained including the finite-size corrections up to $O\left(N^{-1}\right)$.

Figure 2

Theoretical prediction of ${\widehat{E}}_r^{\text{P}}$ for several values of $r$ (solid line), compared with our numerical results. The dashed line is the large-$r$ asymptotic estimate, equal to 1. Error bars do not appear because they are smaller than the marks in the plot. The values for ${\lambda }_r{\widehat{E}}_r^{\mathrm{\Gamma }}$ almost coincide with the values of ${\widehat{E}}_r^{\text{P}}$ (see Table 3) and are not represented.

Figure 3

Numerical estimates of $\mathrm{\Delta }{\widehat{F}}_r^T+\mathrm{\Delta }{\widehat{F}}_r^F$ for several values of $r$ (red squares) and theoretical prediction (blue line) obtained using the law ${\rho }_r^{\text{P}}$. The dashed line is the large-$r$ asymptotic estimate.

Figure 4

Numerical estimates of $\mathrm{\Delta }{\widehat{F}}_r^{\left(1\right)}$ for several values of $r$ (red squares) and theoretical prediction (blue line with circles) obtained using the law ${\rho }_r^{\mathrm{\Gamma }}$. Observe that a discrepancy between the theoretical prediction and the numerical results appears for $r\ge 1$: We interpret this fact as a consequence of the similar scaling of $\mathrm{\Delta }{\widehat{F}}_r^{\left(1\right)}$ and $\mathrm{\Delta }{\widehat{F}}_r^{\left(2\right)}$ for $r\gg 1$, which makes the numerical evaluation of the single contribution $\mathrm{\Delta }{\widehat{F}}^{\left(1\right)}$ difficult. The dashed line is the large-$r$ asymptotic estimate.