Optimality of belief propagation for random assignment problem

MaRDI QIDQ4633825zbMATH OpenFDO

Authors Justin Salez, Devavrat Shah

Publication date 6 May 2019

Full work available at URL https://dl.acm.org/citation.cfm?id=1496792

Mathematics Subject Classification ID

Combinatorial probability (60C05) Analysis of algorithms (68W40) Discrete location and assignment (90B80) Combinatorial optimization (90C27)

Recommendations

• Belief propagation: an asymptotically optimal algorithm for the random assignment problem
• Constructive bounds and exact expectations for the random assignment problem
• The Probabilistic Analysis of a Heuristic for the Assignment Problem
• Average Case Analysis of a Heuristic for the Assignment Problem
• Belief propagation for optimal edge cover in the random complete graph

Cited in

(5)

• Belief propagation for minimum weight many-to-one matchings in the random complete graph
• A Simple Proof for the Optimality of Randomized Posterior Matching
• Belief propagation: an asymptotically optimal algorithm for the random assignment problem
• Belief propagation for optimal edge cover in the random complete graph
• Belief propagation for unbalanced assignment problem

This page was built for publication: Optimality of belief propagation for random assignment problem

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