title: On the expected value of the minimum assignment
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/sub ij/ of X are chosen independently from different distributions. In particular, we require that x/sub ij/ be chosen from the exponential distribution with mean 1/r/sub i/c/sub j/. We conjecture an explicit formula for the expected value of the minimum k-assignment of such X and give evidence for this formula
keyphrases: minimum k-assignment exponential distribution m * n matrix rational function bipartite graph