Physics – Condensed Matter – Disordered Systems and Neural Networks
Scientific paper
2004-07-03
Physics
Condensed Matter
Disordered Systems and Neural Networks
8 pages
Scientific paper
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 cost 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 of matchings in matrices. If this conjecture is proved, this will establish that $\sqrt{n}(A_n - E(A_n)) \overset{w}{\Rightarrow} N(0,2)$. We also establish the limiting distribution for a special case of the Random Assignment Problem.
No associations
LandOfFree
Towards the distribution of the smallest matching in the Random Assignment Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Towards the distribution of the smallest matching in the Random Assignment Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Towards the distribution of the smallest matching in the Random Assignment Problem will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-606775