Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
Proofs of the Parisi and Coppersmith‐Sorkin random assignment conjectures
复制标题
Parisi 和 Coppersmith-Sorkin 随机分配猜想的证明
DOI：
10.1002/rsa.20084
复制
发表时间：
2005
影响因子：
1
通讯作者：
Mayank Sharma
中科院分区：
文献类型：
--
作者：
Chandra Nair;B. Prabhakar;Mayank Sharma
假设有n个作业和n个机器，并且在机器上执行作业的费用涉及确定机器上一对一的作业，以最大程度地减少执行所有作业的成本。 }^n（1/i^2）$。基于Sharma和Prabhakar先前的作品[Proc 40th Annu Allerton Conf Confermance Contractont and Computing，2002，657–666]和Nair [Proc 40th Annu Alnu Allerton Conf Conformance Conlocty and Compucation，2002，667-673]，我们解决了巴黎人和铜匠 - sorkin的猜测
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 $\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