Belief Propagation and LP Relaxation for Weighted Matching in General Graphs

DOI10.1109/TIT.2011.2110170zbMath1366.90202OpenAlexW2167985929MaRDI QIDQ5280978

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

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)

Related Items (5)

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 ⋮ Convergence and correctness of belief propagation for the Chinese postman problem ⋮ 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