We consider the problem of minimizing cost among one-to-one assignments of n jobs onto n machines. The random assignment problem refers to the case when the costs associated with performing jobs on machines are random variables. Aldous established the expected value of the smallest cost, A_n, in the limiting n regime. However the distribution of the minimum cost has not been established yet. In this paper we conjecture some distributional properties concerning matchings in matrices. If this conjecture is proved, this will establish that n~(1/2)(A_n - E(A_n)) => N(0,2). We also establish the limiting distribution for a special case of the Random Assignment Problem.
展开▼
