On the exactness of the cavity method for weighted b-matchings on arbitrary graphs and its relation to linear programs

被引：21

作者：

Bayati, Mohsen ^{[1
]}

Borgs, Christian ^{[1
]}

Chayes, Jennifer ^{[1
]}

Zecchina, Riccardo ^{[2
]}

机构：

[1] Microsoft Res, Cambridge, MA 02142 USA

[2] Politecn Torino, Dept Phys, I-10129 Turin, Italy

来源：

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT | 2008年

关键词：

analysis of algorithms; exact results; message-passing algorithms;

D O I：

10.1088/1742-5468/2008/06/L06001

中图分类号：

O3 [力学];

学科分类号：

08 [工学]; 0801 [力学];

摘要：

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.

引用

收藏

页数：10

相关论文

共 24 条

[1]

The ζ(2) limit in the random assignment problem [J].

Aldous, DJ .

RANDOM STRUCTURES & ALGORITHMS, 2001, 18 (04) :381-418

[2]

Bayati M, 2005, 2005 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), VOLS 1 AND 2, P1763

[3]

BAYATI M, 2007, BELIEF PROPAGATION W

[4]

Max-product for maximum weight matching: Convergence, correctness, and LP duality [J].

Bayati, Mobsen ;

Shah, Devavrat ;

Sharma, Mayank .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2008, 54 (03) :1241-1251

[5]

A simpler max-product Maximum Weight Matching algorithm and the auction algorithm [J].

Bayati, Mohsen ;

Shah, Devavrat ;

Sharma, Mayank .

2006 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, VOLS 1-6, PROCEEDINGS, 2006, :557-+

[6]

Bertsekas D. P., 1988, Annals of Operations Research, V14, P105, DOI 10.1007/BF02186476

[7]

Survey propagation as local equilibrium equations [J].

Braunstein, A ;

Zecchina, R .

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2004,

[8]

Polynomial iterative algorithms for coloring and analyzing random graphs [J].

Braunstein, A ;

Mulet, R ;

Pagnani, A ;

Weigt, M ;

Zecchina, R .

PHYSICAL REVIEW E, 2003, 68 (03) :15

[9]

Survey propagation:: An algorithm for satisfiability [J].

Braunstein, A ;

Mézard, M ;

Zecchina, R .

RANDOM STRUCTURES & ALGORITHMS, 2005, 27 (02) :201-226

[10]

Using linear programming to decode binary linear codes [J].

Feldman, J ;

Wainwright, MJ ;

Karger, DR .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (03) :954-972