The random assignment problem asks for the minimum-cost perfect matching in the complete @math bipartite graph @math with i.i.d. edge weights, say uniform on @math . In a remarkable work by Aldous (2001), the optimal cost was shown to converge to @math as @math , as conjectured by M 'ezard and Parisi (1987) through the so-called cavity method. The latter also suggested a non-rigorous decentralized strategy for finding the optimum, which turned out to be an instance of the Belief Propagation (BP) heuristic discussed by Pearl (1987). In this paper we use the objective method to analyze the performance of BP as the size of the underlying graph becomes large. Specifically, we establish that the dynamic of BP on @math converges in distribution as @math to an appropriately defined dynamic on the Poisson Weighted Infinite Tree, and we then prove correlation decay for this limiting dynamic. As a consequence, we obtain that BP finds an asymptotically correct assignment in @math time only. This contrasts with both the worst-case upper bound for convergence of BP derived by Bayati, Shah and Sharma (2005) and the best-known computational cost of @math achieved by Edmonds and Karp's algorithm (1972).
Although it seems cunningly simple, the assignment problem has led to rich development in combinatorial probability and algorithm design since the early 1960s. Partly motivated to obtain insights for better algorithm design, the question of finding asymptotics of the average cost of @math became of great interest (see @cite_15 @cite_16 @cite_11 @cite_21 @cite_12 @cite_13 @cite_6 ). In 1987, through cavity method based calculations, M 'ezard and Parisi @cite_0 conjectured that, for Exponential(1) edge weights, @math This was rigorously established by Aldous @cite_3 more than a decade later, leading to the formalism of the objective method'' (see survey by Aldous and Steele @cite_19 ). In 2003, an exact version of the above conjecture was independently established by Nair, Prabhakar and Sharma @cite_5 and Linusson and W .astlund @cite_7 .
@cite_7 @cite_21 @cite_6 @cite_3 @cite_0 @cite_19 @cite_5 @cite_15 @cite_16 @cite_13 @cite_12 @cite_11
2141499077 2070993566 1504317671 2065271495
The random assignment problem asks for the minimum-cost perfect matching in the complete n × n bipartite graph Knn with i.i.d. edge weights, say uniform on [0, 1]. In a remarkable work by Aldous [Aldous, D. 2001. The ζ(2) limit in the random assignment problem. RSA18 381--418], the optimal cost was shown to converge to ζ(2) as n → ∞, as conjectured by Mezard and Parisi [Mezard, M., G. Parisi. 1987. On the solution of the random link matching problem. J. Phys.48 1451--1459] through the so-called cavity method. The latter also suggested a nonrigorous decentralized strategy for finding the optimum, which turned out to be an instance of the belief propagation (BP) heuristic discussed by Pearl [Pearl, J. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, San Francisco]. In this paper we use the objective method to analyze the performance of BP as the size of the underlying graph becomes large. Specifically, we establish that the dynamic of BP on Knn converges in distribution as n → ∞ to an appropriately defined dynamic on the Poisson weighted infinite tree, and we then prove correlation decay for this limiting dynamic. As a consequence, we obtain that BP finds an asymptotically correct assignment in O(n2) time only. This contrasts with both the worst-case upper bound for convergence of BP derived by [Bayati, M., D. Shah, M. Sharma. 2008. Max-product for maximum weight matching: Convergence, correctness, and LP duality. IEEE Trans. Inform. Theory54(3) 1241--1251.] and the best-known computational cost of Θ(n3) achieved by Edmonds and Karp's algorithm [Edmonds, J., R. Karp. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM19 248--264]. 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 @math . 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. 2005Supported by the Stanford Graduate Fellowship and Stanford Networking Research Center Grant 1005544-1-WAAXI.Supported in part by the NSF Grant ANI-9985446.Supported by Stanford Office of Technology Grant 2DTA112, Stanford Networking Research Center Grant 1005545-1-WABCJ, and NSF Grant ANI-9985446. Author(s): Aldous, DJ | Abstract: The random assignment (or bipartite matching) problem asks about An = minπ ∑ni=1 c(i, π(i)) where (c(i, j)) is a n × n matrix with i.i.d. entries, say with exponential(1) distribution, and the minimum is over permutations π. Mezard and Parisi (1987) used the replica method from statistical physics to argue nonrigorously that EAn → ζ(2) = π2 6. Aldous (1992) identified the limit in terms of a matching problem on a limit infinite tree. Here we construct the optimal matching on the infinite tree. This yields a rigorous proof of the ζ(2) limit and of the conjectured limit distribution of edge-costs and their rank-orders in the optimal matching. It also yields the asymptotic essential uniqueness property: every almost-optimal matching coincides with the optimal matching except on a small proportion of edges. © 2001 John Wiley a Sons, Inc. Random Struct. Alg., 18, 381-418, 2001. The lower bound 1+1 e+O(n^-^1^+^@e)@k 1.368 is established for the expected minimal cost in the n x n random Assignment Problem where the cost matrix entries are drawn independently from the Uniform(0, 1) probability distribution. The expected number of independent zeroes created in the initial assignment of the Hungarian Algorithm is asymptotically equal to 2-e^-^1^ ^e-e^-^e^^^-^^^1^^^ ^^^e+o(1))[email protected]