Premium
Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
Author(s) -
Nair Chandra,
Prabhakar Balaji,
Sharma Mayank
Publication year - 2005
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20084
Subject(s) - conjecture , mathematics , combinatorics , discrete mathematics , mathematical proof , geometry
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