Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/41604
Title: Relaxed survey propagation: A sum-product algorithm for max-SAT
Authors: Chieu, H.L.
Lee, W.S. 
Issue Date: 2008
Source: Chieu, H.L.,Lee, W.S. (2008). Relaxed survey propagation: A sum-product algorithm for max-SAT. Proceedings of the National Conference on Artificial Intelligence 1 : 247-252. ScholarBank@NUS Repository.
Abstract: The survey propagation (SP) algorithm has been shown to work well on large instances of the random 3-SAT problem near its phase transition. It was shown that SP estimates marginals over covers, using joker states to represent clusters of configurations. The SP-y algorithm generalizes SP to work on the Max-SAT problem, but the cover interpretation of SP does not generalize to SP-y. Recently, a relaxed survey propagation (RSP) algorithm has been proposed for inference in Markov random fields (MRF). RSP for MRFs assigns zero probability to joker states, and hence the cover interpretation is also inapplicable. We adapt RSP to solve Max-SAT problems, and show that it has an interpretation of estimating marginals over covers violating a minimum number of clauses. This naturally generalizes the cover interpretation of SP. Empirically, we show that RSP outperforms SP-y and other state-of-the-art solvers on random as well as benchmark instances of Max-SAT. Copyright © 2008, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Source Title: Proceedings of the National Conference on Artificial Intelligence
URI: http://scholarbank.nus.edu.sg/handle/10635/41604
ISBN: 9781577353683
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

47
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.