Belief Propagation and LP Relaxation for Weighted Matching in General Graphs

DOI10.1109/TIT.2011.2110170zbMATH Open1366.90202OpenAlexW2167985929MaRDI QIDQ5280978FDOQ5280978

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)