A new proof of Parisi´s conjecture for the finite random assignment problem

Consider the problem of minimizing cost when assigning n jobs to n machines. An assignment is a one-to-one mapping of jobs onto the machines. Assume that the cost of executing job i on machine j is C_ij, i,j = 1,...,n. When the c_ij are i.i.d. exponentials of mean 1, Parisi conjectured that the average cost of the minimum assignment equals Σ_i=1ⁿ1/i². Recently, the authors, and independently, Linusson and Wastlund, have proved this conjecture. In the above work the authors also made a refined conjecture that, if established, would yield another proof of the Parisi´s conjecture. This paper establishes the refined conjecture, thus providing a new proof of Parisi´s conjecture.