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
2028955990 2065271495 1504317671 2093966655 1872905819 2070993566 2003351966
The random assignment problem is to choose a minimum-cost perfect matching in a complete n µ n bipartite graph, whose edge weights are chosen randomly from some distribution such as the exponential distribution with mean 1. In this case it is known that the expectation does not grow unboundedly with n, but approaches a limiting value c* between 1.51 and 2. The limit is conjectured to be c* = π 2 6, while a recent conjecture has it that for finite n, the expected cost is EA* = ⌆n i=11 I2. 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] 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. We show that the replica symmetric solution of the matching problem (bipartite or not) with independent random distances is stable. We compute the fluctuations and get the O(1 N) corrections to the length of the optimal matching in a generic sample On montre que la solution symetrique dans les repliques du probleme d'appariement (bipartite ou pas) dans lequel les distances sont des variables aleatoires est stable. On calcule les fluctuations et on obtient les conections d'ordre 1 N pour la longueur de l'appariement optimal dans un echantillon generique This survey describes a general approach to a class of problems that arise in combinatorial probability and combinatorial optimization. Formally, the method is part of weak convergence theory, but in concrete problems the method has a flavor of its own. A characteristic element of the method is that it often calls for one to introduce a new, infinite, probabilistic object whose local properties inform us about the limiting properties of a sequence of finite problems. 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. Given an n by n matrix X, the assignment problem asks for a set of n entries, one from each column and row, with the minimum sum. It is shown that the expected value of this minimum sum is less than 3, independent of n, if X consists of independent random variables uniformly distributed from 0 to 1.