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

DOI10.1287/MOOR.1090.0380MaRDI QIDQ3169045zbMATH OpenOpenAlexFDO

Authors Justin Salez, Devavrat Shah

Publication date 27 April 2011

Published in Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0902.0585

zbMATH Keywords

belief propagationcorrelation decaylocal weak convergencePoisson weighted infinite treerandom assignment problem

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms (68W40) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44)

Abstract: The random assignment problem asks for the minimum-cost perfect matching in the complete $nimesn$ 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 $noinfty$, 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 $Knn$ converges in distribution as $noinfty$ 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).

Recommendations

• Optimality of belief propagation for random assignment problem
• Constructive bounds and exact expectations for the random assignment problem
• Belief propagation for minimum weight many-to-one matchings in the random complete graph
• Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality
• Smoothed analysis of belief propagation for minimum-cost flow and matching

Cited in

(19)

• Belief propagation for the maximum-weight independent set and minimum spanning tree problems
• The planted matching problem: phase transitions and exact results
• Stable matchings in high dimensions via the Poisson-weighted infinite tree
• Belief propagation for minimum weight many-to-one matchings in the random complete graph
• The densest subgraph problem in sparse random graphs
• scientific article; zbMATH DE number 5885078 (Why is no real title available?)
• Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• scientific article; zbMATH DE number 4078841 (Why is no real title available?)
• Replica symmetry of the minimum matching
• Optimality of belief propagation for random assignment problem
• Belief propagation for optimal edge cover in the random complete graph
• The minimum perfect matching in pseudo-dimension \(0<q<1\)
• Belief propagation for MiniMax Weight Matching
• Convergence and Correctness of Max-Product Belief Propagation for Linear Programming
• scientific article; zbMATH DE number 6297707 (Why is no real title available?)
• Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing
• Belief propagation for unbalanced assignment problem
• Local limit of the random degree constrained process
• Ising models on locally tree-like graphs

This page was built for publication: Belief propagation: an asymptotically optimal algorithm for the random assignment problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3169045)