On the fluctuation in the random assignment problem

Abstract

Consider the random assignment (or bipartite matching) problemwith iid uniform edge costs t(i,j). Let A_n be the optimalassignment cost. Just recently does Aldous cite{A2001} givea rigorous proof that EA_n ra zeta(2). In this paper weestablish the upper and lower bounds for text{rm Var} A_n, i.e.,there exist two strictly positive but finite constants C_1and C_2 such thatC_1 n^{-5/2} (log n)^{-3/2} le text{rm Var} A_n le C_2 n^{-1} (log n)^{2}.