Premium
On the expected value of the minimum assignment
Author(s) -
Buck Marshall W.,
Chan Clara S.,
Robbins David P.
Publication year - 2002
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10045
Subject(s) - conjecture , mathematics , combinatorics , value (mathematics) , exponential function , expected value , distribution (mathematics) , matrix (chemical analysis) , exponential distribution , random matrix , discrete mathematics , statistics , mathematical analysis , physics , materials science , composite material , eigenvalues and eigenvectors , quantum mechanics
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