Belief Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions

DOI10.1137/090753115zbMath1225.68130arXiv0709.1190OpenAlexW1761820742WikidataQ61444414 ScholiaQ61444414MaRDI QIDQ3094953

Mohsen Bayati, Riccardo Zecchina, Jennifer T. Chayes, Christian Borgs

Publication date: 27 October 2011

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

matchinglinear programgraph covercavity methodbelief propagation

Mathematics Subject Classification ID

Linear programming (90C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items

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, Replica symmetry of the minimum matching, Hidden Hamiltonian Cycle Recovery via Linear Programming, Weighted matching as a generic pruning technique applied to optimization constraints, Typical performance of approximation algorithms for NP-hard problems, Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension, Convergence and correctness of belief propagation for the Chinese postman problem, The planted k-factor problem

Uses Software

• apcluster
• APCluster