Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures

Suppose that there are n jobs and n machines and it costs cij to execute job i on machine j. The assignment problem concerns the determination of a one‐to‐one assignment of jobs onto machines so as to minimize the cost of executing all the jobs. When the cij are independent and identically distributed exponentials of mean 1, Parisi [Technical Report cond‐mat/9801176, xxx LANL Archive, 1998] made the beautiful conjecture that the expected cost of the minimum assignment equals ∑ᵢ₌₁ⁿ (1/i²) . Coppersmith and Sorkin [Random Structures Algorithms 15 ( 1999 ), 113–144] generalized Parisi's conjecture to the average value of the smallest k‐assignment when there are n jobs and m machines. Building on the previous work of Sharma and Prabhakar [Proc 40th Annu Allerton Conf Communication Control and Computing, 2002 , 657–666] and Nair [Proc 40th Annu Allerton Conf Communication Control and Computing, 2002 , 667–673], we resolve the Parisi and Coppersmith‐Sorkin conjectures. In the process we obtain a number of combinatorial results which may be of general interest.