Page 146 - 《软件学报》2021年第5期

1370 Journal of Software 软件学报 Vol.32, No.5, May 2021

[10] Moskewicz MW, Madigan CF, Zhao Y. Chaff: Engineering an efficient SAT solver. In: Proc. of the 38th Design Automation. 2001.
530−535.
[11] Goldberg E, Novikov Y. BerkMin: A fast and robust SAT-solver. In: Proc. of the Design Automation and Test in Europe. 2002.
142−149.
[12] Eén N, Sörensson N. An Extensible SAT-solver: Theory and Applications of Satisfiability. Berlin: Springer-Verlag, 2004.
502−518.
[13] Zhang H. SATO: An efficient propositional prover. In: Proc. of the Int’l Conf. on Automated Deduction. 1997. 272−275.
[14] Silva JP, Sakallah KA. GRASP: A search algorithm for propositional satisfiability. IEEE Trans. on Computers, 1999,48(5):
506−521.
[15] Selman B, Kautz H, Cohen B. Noise strategies for improving local search. In: Proc. of the AAAI. 1994. 337−343.
[16] Selman B, Levesque HJ, Mitchell D. A new method for solving hard satisfiability problem. In: Proc. of the AAAI. 1992. 440−446.
[17] Pearl J. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufman Publishers, 1988.
[18] Zhao CY, Zheng ZM. A belief-propagation algorithm based on variable entropy for constraint satisfaction problems. SCIENTIA
SINICA Informationis, 2012,42(9):1170−1180 (in Chinese with English abstract).
[19] Yin MH, Zhou JP, Sun JG, Gu WX. Heuristic survey propagation algorithm for solving QBF problem. Ruan Jian Xue Bao/Journal
of Software, 2011,22(7):1538−1550 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/3859.htm [doi: 10.3724/
SP.J.1001.2011.03859]
[20] Ravanbakhsh S, Greiner R. Perturbed message passing for constraint satisfaction problems. Artificial Intelligence, arXiv Preprint
arXiv:1401.6686, 2014.
[21] Chieu HL, Lee WS. Relaxed survey propagation for the weighted maximum satisfiability problem. Journal of Artificial Intelligence
Research, 2009,36(1):229−266.
[22] Bayati M, Shah D, Sharma M. Max product for maximum weight matching: Convergence, correctness, and LP duality. IEEE Trans.
on Information Theory, 2007,54(3):1241−1251.
[23] Coja-Oghlan A, Mossel E, Vilenchik D. A spectral approach to analyzing belief propagation for 3-colouring. Combinatorics,
Probability and Computing, 2009,18(6):881−912.
[24] Gamarnik D, Shah D, Wei Y. Belief propagation for min-cost network flow: Convergence and correctness. Operations Research,
2012,60(2):410−428.
[25] Sanghavi S, Malioutov DM, Willsky AS. Belief propagation and LP relaxation for weighted matching in general graphs. IEEE
Trans. on Information Theory, 2011,57(4):2203−2212.
[26] Sanghavi S, Shah D, Willsky AS. Message passing for maximum weight independent set. IEEE Trans. on Information Theory, 2009,
55(11):4822−4834.
[27] Hetterich S. Analysing survey propagation guided decimation on random formulas. arXiv Preprint arXiv:1602.08519, 2016.
[28] Amin CO. On belief propagation guided decimation for random k-SAT. In: Proc. of the 22nd Annual ACMSIAM Symp. on
Discrete Algorithms. San Francisco, 2016. 957−966.
[29] Marino R, et al. The backtracking survey propagation algorithm for solving random K-SAT problems. Nature Communications,
2016,7:Article No.12996. [doi: 10.1038/ncomms12996(2016)]
[30] Braunstein A, Mezard M, Zecchina R. Survey propagation: An algorithm for satisfiability. Random Structures and Algorithms,
2005,27(2):201−226.
[31] Maneva E, Mossel E, Wainwright M. A new look at survey propagation and its generalizations. Journal of the ACM, 2007,54(4):
1089−1098.
[32] Yedidia JS, Freeman WT, Weiss Y. Understanding belief propagation and its generalizations. Artificial Intelligence, 2003,8(1):
239−269.
[33] Braunstein A, Zecchina R. Survey and belief propagation on random k-SAT. LNCS, 2004,2919(1):519−528.
[34] Weiss Y. Correctness of local probability propagation in graphical models with loops. Neural Computation, 2000,12(1):1−41.
[35] Weiss Y, Freeman WT. Correctness of belief propagation in gaussian graphical models of arbitrary topology. Neural Computation,
2001,13(10):2173−2200.