A proof of Parisi's conjecture on the random assignment problem (Q1434092): Difference between revisions

The authors prove a formula for the expected value of the optimal \(k\)-assignment in a matrix where some of the entries are zero, and all the other entries are independent exponentially distributed random variables with mean 1. An assignment problem is the optimization problem of finding, in an \(m\)-by-\(n\) matrix of nonnegative real numbers, \(k\) entries, no two in the same row or column, such that their sum is minimal. In consequence, in the paper, the authors prove the Parisi's conjecture for the case \(k= m= n\), as well as the generalized conjecture of Coppersmith and Sorkin for arbitrary \(k\), \(m\), and \(n\).