ON THE FLUCTUATION IN THE RANDOM ASSIGNMENT PROBLEM
Sung-Chul Lee, Zhonggen Su · Communications of the Korean Mathematical Society · 2002
Consider the random assignment (or bipartite matching) problem with iid uniform edge costs t(i, j). Let $A_{n}$ be the optimal assignment cost. Just recently does Aldous [2] give a rigorous proof that E $A_{n}$ longrightarrowζ(2). In this paper we establish the upper and lower bounds for Var $A_{n}$ , i.e., there exist two strictly positive but finite constants $C_1$ and $C_2$ such athat $C_1$ $n^{(-5}$ 2)/ (log n) $^{(-3}$ 2)/ $\leq$ Var $A_{n}$ $\leq$ $C_2$ $n^{-1}$ (log n) $^2$ .EX>.