Problems / probability-statistics
probability-statistics / Random combinatorial optimization
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. Aldous proved in 1992 that $\mathbb{E}[C_n]$ converges, later identifying the limit as $\zeta(2)$ via the Poisson-weighted infinite tree; Parisi's exact finite-$n$ formula for exponential costs was then proved by Linusson-Wästlund and independently by Nair, Prabhakar and Sharma. The fluctuations resisted. Talagrand applied product-space concentration, Wästlund computed the exponential model's variance as $4\zeta(2)-4\zeta(3)+O(n^{-2})$, and Chatterjee proved an order-$n^{-1/2}$ lower bound under tail hypotheses that exclude the bounded uniform law - but no central limit theorem for $C_n$ was known. This paper claims one: $\sqrt{n}\,(C_n-\zeta(2)) \Rightarrow \mathcal{N}(0,\,4\zeta(2)-4\zeta(3))$.