Please use this identifier to cite or link to this item:
Title: Relaxed survey propagation for the weighted maximum satisfiability problem
Authors: Chieu, H.L.
Lee, W.S. 
Issue Date: 2009
Source: Chieu, H.L.,Lee, W.S. (2009). Relaxed survey propagation for the weighted maximum satisfiability problem. Journal of Artificial Intelligence Research 36 : 229-266. 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 that represent clusters of solutions. The SP-y algorithm generalizes SP to work on the maximum satisfiability (Max-SAT) problem, but the cover interpretation of SP does not generalize to SP-y. In this paper, we formulate the relaxed survey propagation (RSP) algorithm, which extends the SP algorithm to apply to the weighted Max-SAT problem. We show that RSP has an interpretation of estimating marginals over covers violating a set of clauses with minimal weight. This naturally generalizes the cover interpretation of SP. Empirically, we show that RSP outperforms SP-y and other state-of-the-art Max-SAT solvers on random Max-SAT instances. RSP also outperforms state-of-the-art weighted Max-SAT solvers on random weighted Max-SAT instances. © 2009 AI Access Foundation.
Source Title: Journal of Artificial Intelligence Research
ISSN: 10769757
DOI: 10.1613/jair.2808
Appears in Collections:Staff Publications

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


checked on Dec 4, 2017

Page view(s)

checked on Dec 8, 2017

Google ScholarTM



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