document: On the expected value of the minimum assignment 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
doc_bio_tags: O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O B I O O O O O O O O O O O O O O O O O O O O O O O O O O O O O