Belief propagation : an asymptotically optimal algorithm for the random assignment problem

Justin Salez 1 Devavrat Shah 2
1 TREC - Theory of networks and communications
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt
Abstract : The random assignment problem asks for the minimum-cost perfect matching in the complete $n\times n$ bipartite graph $\Knn$ with i.i.d. edge weights, say uniform on $[0,1]$. In a remarkable work by Aldous (2001), the optimal cost was shown to converge to $\zeta(2)$ as $n\to\infty$, as conjectured by Mézard 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 $\Knn$ converges in distribution as $n\to\infty$ 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(n^2)$ 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 $\Theta(n^3)$ achieved by Edmonds and Karp's algorithm (1972).
Type de document :
Article dans une revue
Mathematics of Operations Research, INFORMS, 2009
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Justin Salez <>
Soumis le : mardi 3 février 2009 - 13:15:04
Dernière modification le : jeudi 11 janvier 2018 - 06:20:06
Document(s) archivé(s) le : mardi 8 juin 2010 - 19:08:07


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00358331, version 1
  • ARXIV : 0902.0585



Justin Salez, Devavrat Shah. Belief propagation : an asymptotically optimal algorithm for the random assignment problem. Mathematics of Operations Research, INFORMS, 2009. 〈inria-00358331〉



Consultations de la notice


Téléchargements de fichiers