On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs

Details 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

2008-07-20

arxiv.org/abs/0807.3159v1

J. Stat. Mech. (2008) L06001

Physics

Condensed Matter

Statistical Mechanics

Scientific paper

10.1088/1742-5468/2008/06/L06001

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.

Affiliated with

Also associated with

No associations

Rating

On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-420163