- The Experience
- The Programs
- MBA Program
- MSx Program
- PhD Program
- Executive Education
- Stanford Ignite
- Research Fellows Program
- Summer Institute for General Management
- Stanford LEAD Certificate: Corporate Innovation
- Stanford Innovation & Entrepreneurship Certificate
- Executive Program for Nonprofit Leaders
- Executive Program in Social Entrepreneurship
- Executive Program for Education Leaders
- Stanford go.to.market
- Faculty & Research
- Insights
- Alumni
- Events
You are here
On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
Journal of Statistical Mechanics: Theory and Experiment. July
20, 2008
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.