Published June 2008
| Version v1
Journal article
On the exactness of the cavity method for weighted b-matchings on arbitrary graphs and its relation to linear programs
- 1. Microsoft Research, One Memorial Dr., Cambridge, MA 02142 (United States)
- 2. Physics Department, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino (Italy)
Description
We consider the general problem of finding the minimum weight b-matching on arbitrary graphs. We prove that, whenever the linear programing 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. (letter)
Availability note (English)
Available from http://dx.doi.org/10.1088/1742-5468/2008/06/L06001Additional details
Identifiers
- DOI
- 10.1088/1742-5468/2008/06/L06001;
- PII
- S1742-5468(08)82163-2;
Publishing Information
- Journal Title
- Journal of Statistical Mechanics
- Journal Volume
- 2008
- Journal Issue
- 06
- Journal Page Range
- [10 p.]
- ISSN
- 1742-5468
INIS
- Country of Publication
- United Kingdom
- Country of Input or Organization
- International Atomic Energy Agency (IAEA)
- INIS RN
- 44106978
- Subject category
- S97: MATHEMATICAL METHODS AND COMPUTING;
- Descriptors DEI
- EQUATIONS; GRAPH THEORY; LINEAR PROGRAMMING; MATHEMATICAL SOLUTIONS; RELAXATION
- Descriptors DEC
- CALCULATION METHODS; MATHEMATICS