A message-passing algorithm with damping

被引:77
作者
Pretti, M [1 ]
机构
[1] Politecn Torino, Dipartimento Fis, I-10129 Turin, Italy
来源
JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT | 2005年
关键词
message-passing algorithms; new applications of statistical mechanics;
D O I
10.1088/1742-5468/2005/11/P11008
中图分类号
O3 [力学];
学科分类号
08 ; 0801 ;
摘要
We propose a modified belief propagation algorithm, with overrelaxed dynamics. Such an algorithm turns out to be generally more stable and faster than ordinary belief propagation. We characterize the performance of the algorithm, employed as a tool for combinatorial optimization, on the random satisfiability problem. Moreover, we trace a connection with a recently proposed double-loop algorithm for minimizing Bethe and Kikuchi free energies.
引用
收藏
页码:165 / 179
页数:15
相关论文
共 31 条
[1]   A NOTE ON THE CLUSTER VARIATION METHOD [J].
AN, GZ .
JOURNAL OF STATISTICAL PHYSICS, 1988, 52 (3-4) :727-734
[2]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[3]  
[Anonymous], 1935, P ROY SOC A-MATH PHY, DOI DOI 10.1098/RSPA.1935.0122
[4]  
Battaglia D, 2004, PHYS REV E, V70, DOI 10.1103/PhysRevE.70.036107
[5]  
BRAUNSTEIN A, 2002, CSCC0212002
[6]  
BURLEY DM, 1972, PHASE TRANSITIONS CR, V2, pCH9
[7]  
Cook S. A., 1971, P 3 ANN ACM S THEOR, P151, DOI DOI 10.1145/800157.805047
[8]   THEORY OF SPIN GLASSES [J].
EDWARDS, SF ;
ANDERSON, PW .
JOURNAL OF PHYSICS F-METAL PHYSICS, 1975, 5 (05) :965-974
[9]  
Heskes T., 2003, P 19 ANN C UNC ART I, P313
[10]  
Kappen HJ, 2002, ADV NEUR IN, V14, P415