A Proof of Parisi's Conjecture on the Random Assignment Problem
Linusson, Svante ; Waestlund, Johan
arXiv, 0303214 / Harvested from arXiv
Text on arXiv
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. Such an optimization problem is called a random assignment problem if the matrix entries are random variables. We give a formula for the expected value of the optimal k-assignment in a matrix where some of the entries are zero, and all other entries are independent exponentially distributed random variables with mean 1. Thereby we prove the formula 1+1/4+1/9+...+1/k^2 conjectured by G. Parisi for the case k=m=n, and the generalized conjecture of D. Coppersmith and G. B. Sorkin for arbitrary k, m and n.
Publié le : 2003-03-18
Classification:  Mathematics - Combinatorics,  Mathematical Physics,  Mathematics - Probability 
@article{0303214,
     author = {Linusson, Svante and Waestlund, Johan},
     title = {A Proof of Parisi's Conjecture on the Random Assignment Problem},
     journal = {arXiv},
     volume = {2003},
     number = {0},
     year = {2003},
     language = {en},
     url = {http://dml.mathdoc.fr/item/0303214}
}

Linusson, Svante; Waestlund, Johan. A Proof of Parisi's Conjecture on the Random Assignment Problem. arXiv, Tome 2003 (2003) no. 0, . http://gdmltest.u-ga.fr/item/0303214/