A central limit theorem for the random assignment problem

Abstract

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-path selection of an optimal dual potential. After the unused reduced costs are integrated out, a reference law separates the rows conditionally on the potential field, while the ordered potential gaps become independent exponentials. The only residual dependence is a directed-tree factor. Ordering the potentials turns its zero--one support into a Ferrers matrix, whose matrix-tree determinant is triangular. A singular inverse-degree estimate and exact normalization then yield total-variation convergence to the reference law. Finally, a conditional triangular-array central limit theorem accounts for row noise, and a second triangular array accounts for the linear response of the potential field. The strategy used here is likely to be applicable to other problems.