A generalization of the random assignment problem

Svante Linusson Johan Wästlund

To appear at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), May 20-26, 2001


We give a conjecture for the expected value of the optimal k-assignment in an m times n matrix, where the entries are all exp(1)-distributed random variables or zeros. This conjecture generalizes a conjecture of Coppersmith and Sorkin. We prove this conjecture for the case that there is a zero-cost k-1-assignment. Assuming our conjecture, we determine some limits, as k=m=n tends to infinity, of the expected cost of an optimal n-assignment in an n by n matrix with zeros in a given region. If we take the region outside a quarter-circle inscribed in the square matrix, this limit is thus conjectured to be Pi^2/24.

Server START Conference Manager
Update Time 23 Feb 2001 at 08:48:04
Maintainer maylis@labri.u-bordeaux.fr.
Start Conference Manager
Conference Systems