Belief Propagation and LP Relaxation for Weighted Matching in General Graphs

DOI10.1109/TIT.2011.2110170MaRDI QIDQ5280978zbMATH OpenOpenAlexFDO

Authors Sujay Sanghavi, Dmitry M. Malioutov, Alan S. Willsky

Publication date 27 July 2017

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

Full work available at URL https://doi.org/10.1109/tit.2011.2110170

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited in

(8)

• Convergence and correctness of belief propagation for weighted min-max flow
• Convergence and correctness of belief propagation for the Chinese postman problem
• Belief propagation for minimum weight many-to-one matchings in the random complete graph
• 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
• Convergence and Correctness of Max-Product Belief Propagation for Linear Programming
• Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
• A new distributed approximation algorithm for the maximum weight independent set problem

This page was built for publication: Belief Propagation and LP Relaxation for Weighted Matching in General Graphs

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