More generally, one can define a weighted version of MAX-SAT as follows: given a conjunctive normal form formula with non-negative weights assigned to each clause, find truth values for its variables that maximize the combined weight of the satisfied clauses. The MAX-SAT problem is an instance of Weighted MAX-SAT where all weights are 1.
Approximation algorithms 1, 2, ..., n, -->
1/2-approximation Randomly assigning each variable to be true with probability 1/2 gives an
expected 2-approximation. More precisely, if each clause has at least variables, then this yields a (1 − 2−)-approximation. This algorithm can be
derandomized using the
method of conditional probabilities.
(1-1/)-approximation MAX-SAT can also be expressed using an
integer linear program (ILP). Fix a conjunctive normal form formula with variables 1, 2, ..., n, and let denote the clauses of . For each clause in , let + and − denote the sets of variables which are not negated in , and those that are negated in , respectively. The variables of the ILP will correspond to the variables of the formula , whereas the variables will correspond to the clauses. The ILP is as follows: The above program can be
relaxed to the following linear program : The following algorithm using that relaxation is an expected (1-1/
e)-approximation: • Solve the linear program and obtain a solution • Set variable to be true with probability where is the value given in . This algorithm can also be derandomized using the method of conditional probabilities.
3/4-approximation The 1/2-approximation algorithm does better when clauses are large whereas the (1-1/)-approximation does better when clauses are small. They can be combined as follows: • Run the (derandomized) 1/2-approximation algorithm to get a truth assignment . • Run the (derandomized) (1-1/e)-approximation to get a truth assignment . • Output whichever of or maximizes the weight of the satisfied clauses. This is a deterministic factor (3/4)-approximation.
Example On the formula :F=\underbrace{(x\lor y)}_{\text{weight }1}\land \underbrace{(x\lor\lnot y)}_{\text{weight }1}\land\underbrace{(\lnot x\lor z)}_{\text{weight }2+\epsilon} where \epsilon >0, the (1-1/)-approximation will set each variable to True with probability 1/2, and so will behave identically to the 1/2-approximation. Assuming that the assignment of is chosen first during derandomization, the derandomized algorithms will pick a solution with total weight 3+\epsilon, whereas the optimal solution has weight 4+\epsilon.
State of the art The state-of-the-art algorithm is due to Avidor, Berkovitch and Zwick, and its approximation ratio is 0.7968. They also give another algorithm whose approximation ratio is conjectured to be 0.8353. ==Solvers==