Gilles Mordant

A central limit theorem for the random assignment problem

Let \(C_n\) be the minimum cost of a perfect matching in an \(n\times n\) matrix of independent uniform random variables. We prove that \[ \sqrt n\{C_n-\zeta(2)\} \ \Longrightarrow\ \mathcal N\bigl(0,4\zeta(2)-4\zeta(3)\bigr). \] The proof begins with an exact change of variables based on a uniformly rooted shortest-pa...