Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality

DOI10.1109/TIT.2007.915695zbMath1311.90161arXivcs/0508101MaRDI QIDQ3604573

Devavrat Shah, Mohsen Bayati, M. Sharma

Publication date: 24 February 2009

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (12)

Belief propagation for the maximum-weight independent set and minimum spanning tree problems ⋮ Optimizing social welfare for network bargaining games in the face of instability, greed and idealism ⋮ On Resolving Simultaneous Congruences Using Belief Propagation ⋮ Random-link matching problems on random regular graphs ⋮ Belief propagation for optimal edge cover in the random complete graph ⋮ The patient-zero problem with noisy observations ⋮ Fast Fitness Improvements in Estimation of Distribution Algorithms Using Belief Propagation ⋮ The importance of memory for price discovery in decentralized markets ⋮ Bargaining dynamics in exchange networks ⋮ Convergence and correctness of belief propagation for the Chinese postman problem ⋮ The random fractional matching problem ⋮ Gauges, loops, and polynomials for partition functions of graphical models

This page was built for publication: Max-Product for Maximum Weight Matching: Convergence, Correctness, and LP Duality