Random Assignment with Integer Costs
Robert Parviainen · Combinatorics Probability Computing · 2004
The random assignment problem is to minimize the cost of an assignment in an $n\times n$ matrix of random costs. In this paper we study the problem for some integer-valued cost distributions. We consider both uniform distributions on $1,2,\dots ,m$ , for $m=n$ or $n^2$ , and random permutations of $1,2,\dots ,n$ for each row, or of $1,2,\dots ,n^2$ for the whole matrix. We find the limit of the expected cost for the ‘ $n^2$ ’ cases, and prove bounds for the ‘ $n$ ’ cases. This is done by simple coupling arguments together with recent results of Aldous for the continuous case. We also present a simulation study of these cases.