Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem

DOI10.1287/MOOR.1090.0380zbMath1230.68183arXiv0902.0585OpenAlexW2141499077MaRDI QIDQ3169045

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

local weak convergencebelief propagationcorrelation decayPoisson weighted infinite treerandom assignment problem

Mathematics Subject Classification ID

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

Related Items (9)

Belief propagation for the maximum-weight independent set and minimum spanning tree problems ⋮ Stable matchings in high dimensions via the Poisson-weighted infinite tree ⋮ Convergence and Correctness of Max-Product Belief Propagation for Linear Programming ⋮ Replica symmetry of the minimum matching ⋮ Belief propagation for optimal edge cover in the random complete graph ⋮ Ising models on locally tree-like graphs ⋮ The planted matching problem: phase transitions and exact results ⋮ The minimum perfect matching in pseudo-dimension 0 < q < 1 ⋮ The densest subgraph problem in sparse random graphs

This page was built for publication: Belief Propagation: An Asymptotically Optimal Algorithm for the Random Assignment Problem