The \(\zeta(2)\) limit in the random assignment problem (Q2746215)

Let us consider the task of choosing an assignment of \(n\) jobs to machines in order to minimize the total cost of performing the \(n\) jobs. The basic input for the problem is an \(n\times n\) matrix \((c(i,j))\), where \(c(i,j)\) is viewed as the cost of performing job \(i\) on machine \(j\), and the assignment problem is to determine a permutation \(\pi\) that solves \(A_n=\min\pi\sum^n_{i=1}c(i,\pi(i))\). \textit{M. Mezard} and \textit{G. Parisi} [J. Phys. 48, 1451-1459 (1987)] and the author [Probab. Theory Relat. Fields 93, No. 4, 507-534 (1992; Zbl 0767.60006)] argued nonrigorously that \(\lim_n EA_n=\pi^2/6=\zeta(2)\).NEWLINENEWLINENEWLINEIn this paper the author continues the weak convergence analysis mentioned above. He constructs the optimal matching on the infinite tree. This yields a rigorous proof of the \(\zeta(2)\) limit and of the conjectured limit distribution of edge-costs and their rank-orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost-optimal matching coincides with the optimal matching except on a small proportion of edges.