Computer Science ›› 2015, Vol. 42 ›› Issue (1): 279-284.doi: 10.11896/j.issn.1002-137X.2015.01.062

Previous Articles     Next Articles

Convergence of Warning Propagation Algorithm for Regular Structure Instances

WANG Xiao-feng, LI Qiang and DING Hong-sheng   

  • Online:2018-11-14 Published:2018-11-14

Abstract: Message propagation algorithms are very effective in finding satisfying assignments for 3-SAT instances,and they can make hard region become narrower.However,message propagation algorithms do not always converge for graphs with cycles.Unfortunately,rigorous theory proof of this phenomenon is still lacking.Warning propagation algorithm is the most basic message propagation algorithm,and we analysed convergence of the warning propagation algorithm.Lastly,experimental results show that convergence of the warning propagation algorithm is improved for (3,4)-SAT instances.

Key words: Warning propagation algorithm,Convergence,Satisfiability problems,Regular structure

[1] Martin D,Alan F,Michael M.A probabilistic analysis of randomly generated binary constraint satisfaction[J].Theory Computer Science,2003,290:1815-1828
[2] Creignou N,Eaude H.The SAT-UNSAT transition for random constraint satisfaction problems[J].Discrete Mathematics,2009,309:2085-2099
[3] Martin O C,Monasson R,Zecchina R.Statistical mechanicsmethods and phase transitions in optimization[J].Theory Computer Science,2001,265:3-67
[4] Tsang E.A glimpse of constraint satisfaction[J].Artificial Intelligence Review,1999,13:215-277
[5] Bourgain J.Sharp thresholds of graph properties and the k-SATproblem[J].Journal of The American Mathematical Society,1999,2(4):1017-1054
[6] Kirkpatrick S,Selman B.Critical behavior in the satisfiability of random Boolean Formulae[J].Science,1994,4(5163):1297-1301
[7] Mertens S,Mezard M,Zecchina R.Threshold values of random k-SAT from the cavity method[J].Random Structure Algorithms,2006,28:340-373
[8] Kaporis A,Kirousis L,Lalas E.The probabilistic analysis of agreedy satisfiability algorithm[J].Random structures & Algorithms,2006,8(4):444-480
[9] Dubois O,Boufkhad Y,Mandler J.Typical random 3-sat formulae and the satisfiability threshold[J].Electronic Colloquium on Computational Complexity,2003,10(7):1-2
[10] Moskewicz M W,Madigan C F,Zhao Y.Chaff:Engineering an efficient SAT solver[C]∥Proceedings of the 38th annual Design Automation Conference.New York,ACM,2001:530-535
[11] Aurell E,Gordon U,Kirkkpatrick S.Comparing beliefs,sur-veys,and random walks[J].Advances in Neural Information Processing Systems,2004,7(1):1-8
[12] Mezard M,Parisi G.The cavity method at zero temperature[J].Journal of Statistical Physics,2003,111(1/2):1-34
[13] Mezard M,Zecchina R.Random k-satisifability problem:Froman analytic solution to an efficient algorithm[J].Physical Review E,2002,6(5):56-126
[14] Maneva E,Mossel E,Wainwright M.A new look at surveypropagation and its generalizations[J].Journal of the ACM,2007,4(4):1089-1098
[15] Braunstein A,Mezard M,Zecchina R.Survey propagation:An algorithm for satisfiability[J].Random Structures and Algorithms,2005,7(2):201-226
[16] Montanari A.Message passing algorithms:A success looking for theoreticians[C]∥Proc.of the 42nd ACM Symposium on Theory of Computing (STOC 2010).New York,ACM,2010:37-38
[17] Yedidia J S,Freeman W T,Weiss Y.Understanding belief propa-gation and its generalizations[J].Artificial Intelligence,2003,8(1):239-269
[18] Mezard M,Parisi G,Zecchina R.Analytic and algorithmic solution of random satisfiability problems[J].Science,2002,7(5582):812-815
[19] Cjavas J,Furtlehner C,Mezard M,et al.Survey propagation decimation through distributed local computations[J].Journal of Statistic Mathematics,2005,2005(11):11016
[20] Braunstein A,Zecchina R.Survey and belief propagation on random k-SAT[J].Lecture Notes in Computer Science,2004,9(1):519-528
[21] Xu Ke,Li Wei.Exact phase transitions in random constraint sa-tisfaction problems[J].Journal of Artificial Intelligence Research,2000,12(1):93-103
[22] Xu Ke,Li Wei.Many hard examples in exact phase transitions[J].Theory Computer Science,2006,355(1):291-302
[23] Xu Ke,Boussemart F,Hemery F,et al.Random constraint satisfaction:Easy generation of hard instances[J].Artificial Intelligence,2007,171(1):514-534
[24] 赵春艳,郑志明.一种基于变量熵求解约束满足问题的置信传播算法[J].中国科学F:信息科学,2012,2(9):1170-1180
[25] 殷明浩,周俊萍,孙吉贵,等.求解 QBF 问题的启发式调查传播算法[J].软件学报,2011,2(7):1538-1550
[26] Kschischang F,Frey B,Loeliger H.Factor graph and the sum-product algorithm[J].Information Theory,2001,47(1):498-519
[27] Weiss Y.Correctness of local probability propagation in gra-phical models with loops[J].Neural Computation,2000,2(1):1-41
[28] Weiss Y,Freeman W T.Correctness of belief propagation inGaussian graphical models of arbitrary topology[J].Neural Computation,2001,13(10):2173-2200
[29] Tatikonda S,Jordan M I.Loopy belief propagation and Gibbs measure[C]∥Proceedings of the 18th Annual Conference on Uncertainty in Artificial Intelligence.2002:493-500
[30] Heskes T.On the uniqueness of loopy belief propagation fixed points[J].Neural Computation,2004,16:2379-2413
[31] Ihler A T.Loopy belief propagation:Convergence and effects of message errors[J].Machine Learning Research,2005,6:905-936
[32] Mooij J M,Kappen H J.Sufficient conditions for convergence of the sum-product algorithm[J].IEEE Transactions on Information Theory,2007,3:4422-4437
[33] Shi Xiang-qiong,Schonfeld D,Tuninetti D.Message error analysis of loopy belief propagation for the sum-product algorithm[J].Computer and Information Science,2010,1009:1-30
[34] Gamarnik D,Shah D,Wei Y.Belief propagation for min-costnetwork flow:Convergence and correctness[J].Operations Research,2012,0(2):410-428
[35] Brunsch T,Cornelissen K,Manthey B,et al.Smoothed analysis of BP for minimum cost flow and matching[J].Journal of Graph Algorithms and Applications,2013,7(6):647-670
[36] Norshams N,Wainwright M J.Stochastic belief propagation:A low complexity alternative to the sum product algorithm[J].IEEE Transactions on Information Theory,2013,9(4):1981-2000
[37] Feige U,Mossel E,Vilenchik D.Complete convergence of message passing algorithms for some satisfiability problems[J].Theory of computing,2013,9(19):617-651
[38] 王晓峰,许道云,韦立.随机可满足实例集上警示传播算法的收敛性[J].软件学报,2013,24(1):1-11
[39] 许道云,王晓峰.一个正则NP-完全问题及其不可近似性[J].计算机科学与探索,2013,7(8):691-697

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!