On the expected value of the minimum assignment

Abstract

Abstract The minimum k ‐assignment of an m × n matrix X is the minimum sum of k entries of X, no two of which belong to the same row or column. Coppersmith and Sorkin conjectured that if X is generated by choosing each entry independently from the exponential distribution with mean 1, then the expected value of its minimum k ‐assignment is given by an explicit formula, which has been proven only in a few cases. In this paper we describe our efforts to prove the Coppersmith–Sorkin conjecture by considering the more general situation where the entries x ij of X are chosen independently from different distributions. In particular, we require that x ij be chosen from the exponential distribution with mean 1/ r i c j . We conjecture an explicit formula for the expected value of the minimum k ‐assignment of such X and give evidence for this formula. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 33–58, 2002