Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures

摘要

Suppose that there are it 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 Sigma(i=l)(n) (1/i(2)). Coppersmith and Sorkin [Random Structures Algorithms 15 (1999)7 113-144] generalized Parisi's conjecture to the average value of the smallest k-assignment when there are it jobs and in 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. (c) 2005 Wiley Periodicals, Inc.