  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.
