A rigorous analysis of the cavity equations for the minimum spanning tree

被引：14

作者：

Bayati, Mohsen ^{[1
]}

Braunstein, Alfredo ^{[2
]}

Zecchina, Riccardo ^{[2
]}

机构：

[1] Microsoft Res, Redmond, WA 98052 USA

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

来源：

JOURNAL OF MATHEMATICAL PHYSICS | 2008年 / 49卷 / 12期

关键词：

topology; trees (mathematics);

D O I：

10.1063/1.2982805

中图分类号：

O4 [物理学];

学科分类号：

0702 ;

摘要：

We analyze a new general representation for the minimum weight Steiner tree problem that translates the topological connectivity constraint into a set of local conditions, which can be analyzed by the so-called cavity equation techniques. For the limit case of the spanning tree, we prove that the fixed point of the algorithm arising from the cavity equations leads to the global optimum.

引用

收藏

页数：6

相关论文

共 16 条

[1]

[Anonymous], COMPLEXITY COMPUTER

[2] Statistical mechanics of Steiner trees [J].

Bayati, M. ;

Borgs, C. ;

Braunstein, A. ;

Chayes, J. ;

Ramezanpour, A. ;

Zecchina, R. .

PHYSICAL REVIEW LETTERS, 2008, 101 (03)

[3]

BAYATI M, ARXIV07091190

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

Bayati, Mohsen ;

Borgs, Christian ;

Chayes, Jennifer ;

Zecchina, Riccardo .

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT, 2008,

[5] Learning by message passing in networks of discrete synapses [J].

Braunstein, A ;

Zecchina, R .

PHYSICAL REVIEW LETTERS, 2006, 96 (03)

[6] 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

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

Braunstein, A ;

Mézard, M ;

Zecchina, R .

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

[8]

Di CY, 2004, 2004 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, PROCEEDINGS, P102

[9] Clustering by passing messages between data points [J].

Frey, Brendan J. ;

Dueck, Delbert .

SCIENCE, 2007, 315 (5814) :972-976

[10] Gibbs states and the set of solutions of random constraint satisfaction problems [J].

Krzakala, Florent ;

Montanari, Andrea ;

Ricci-Tersenghi, Federico ;

Semerjian, Guilhem ;

Zdeborova, Lenka .

PROCEEDINGS OF THE NATIONAL ACADEMY OF SCIENCES OF THE UNITED STATES OF AMERICA, 2007, 104 (25) :10318-10323