On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
arXiv:0807.3159 · doi:10.1088/1742-5468/2008/06/L06001
Abstract
We consider the general problem of finding the minimum weight b-matching on arbitrary graphs. We prove that, whenever the linear programming relaxation of the problem has no fractional solutions, then the cavity or belief propagation equations converge to the correct solution both for synchronous and asynchronous updating.
References in corpus (7)
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Maximum Weight Matching via Max-Product Belief Propagation
- Survey propagation: an algorithm for satisfiability
- The number of matchings in random graphs
- Survey Propagation as local equilibrium equations
- Polynomial iterative algorithms for coloring and analyzing random graphs
- Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
Cited by in corpus (17)
- Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
- A rigorous analysis of the cavity equations for the minimum spanning tree
- MAP Estimation, Message Passing, and Perfect Graphs
- A Natural Dynamics for Bargaining on Exchange Networks
- Statistical mechanics of budget-constrained auctions
- Convergence of multivariate belief propagation, with applications to cuckoo hashing and load balancing
- Inference-Based Distributed Channel Allocation in Wireless Sensor Networks
- On MAP Inference by MWSS on Perfect Graphs
- Next nearest neighbour Ising models on random graphs
- Replica Symmetry and Combinatorial Optimization
- Classification and sparse-signature extraction from gene-expression data
- An FPTAS for Bargaining Networks with Unequal Bargaining Powers
- Belief Propagation for Min-cost Network Flow: Convergence and Correctness
- Bargaining dynamics in exchange networks
- Convergence of Local Dynamics to Balanced Outcomes in Exchange Networks
- Correlation Decay in Random Decision Networks
- Belief Propagation Min-Sum Algorithm for Generalized Min-Cost Network Flow