Skip to Main content Skip to Navigation
Journal articles

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, 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).
Document type :
Journal articles
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00358331
Contributor : Justin Salez <>
Submitted on : Tuesday, February 3, 2009 - 1:15:04 PM
Last modification on : Thursday, July 1, 2021 - 5:58:02 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 7:08:07 PM

Files

BP1.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

289

Files downloads

750