Random Assignment with Integer Costs

Abstract

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.