# Approximation Algorithms for MAXSAT

Trying to find the optimal solution to WEIGHTED-MAX-3SAT, the weighted version of the 3-SAT optimization problem, is NP-hard. In fact, even approximating the non-weighted version of MAX-SAT arbitrarily well is provably NP-hard by the PCP Theorem.

A canonical algorithm for approximating WEIGHTED-MAX-3SAT is MAX-WalkSAT. Looking around I found some information on other algorithms (i.e. branch-and-bound, the DPL algorithm) which are commonly used to find solutions to 3-SAT or (unweighted) MAX-3SAT, but I didn't see any discussion of how well these would work for the weighted version. Intuitively, without being adapted they would not work as well.

I'm wondering what other algorithms are commonly used to approximate WEIGHTED-MAX-SAT, if there are well-known WEIGHTED-MAX-SAT solvers, and the relative quality of these algorithms/solvers.

• This is not really on topic as it is asking about heuristics and implementation experience rather than provable algorithms. Commented Oct 9, 2010 at 14:43
• @Warren: I think perhaps that is taking things a little too far. The question basically amounts to "What algorithms are good for WEIGHTED-MAX-SAT?" which is a perfectly reasonable question to ask. Many SAT solvers rely on heuristics too. Even though their worst case performance is poor, they do surprisingly well. If every question related to only exactly proved complexity results, I doubt the site would be very popular. After all, we already have the zoo. Commented Oct 10, 2010 at 0:43
• The MAXSAT competition has divisions for weighted and for unweighted: maxsat.udl.cat/10/results Commented Oct 11, 2010 at 17:35
• Here's one readable description of one of the algorithms used: scholar.google.com/scholar?cluster=14077294269217865108 Commented Oct 11, 2010 at 17:38
• @Warren: In the '80s and '90s, at many universities, theoretical computer science was very unpopular and looked down upon by the rest of computer science because it was viewed as unconnected to practice. Eventually, Google and other successes convinced them that we were worth talking to. Let's please not close off the lines of communication from the other side now, after having worked so long to open them. That would be very bad for the field, not to mention the TCS job market. Commented Oct 20, 2010 at 14:16