Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures

Suppose that there are n jobs and n machines and it costs c ij 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 c ij 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 $\sum_{i=1}^n (1/i^2)$ . 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.© 2005 Wiley Periodicals, Inc. Random Struct. Alg. 2005