Title :
A new proof of Parisi´s conjecture for the finite random assignment problem
Author :
Nair, Chandra ; Prabhakar, Balaji ; Sharma, Mayank
Author_Institution :
Dept. of Electr. Eng., Stanford Univ., CA, USA
fDate :
27 June-2 July 2004
Abstract :
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 Cij, i,j = 1,...,n. When the cij are i.i.d. exponentials of mean 1, Parisi conjectured that the average cost of the minimum assignment equals Σi=1n1/i2. 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.
Keywords :
information theory; matrix algebra; random processes; Parisi´s conjecture; finite random assignment problem; job execution; one-to-one mapping; Costs; Distributed computing; Exponential distribution; Random variables;
Conference_Titel :
Information Theory, 2004. ISIT 2004. Proceedings. International Symposium on
Print_ISBN :
0-7803-8280-3
DOI :
10.1109/ISIT.2004.1365098