- INSTANCE:
Set
*U*of variables, collection*C*of disjunctive clauses of at most*k*literals, where a literal is a variable or a negated variable in*U*.*k*is a constant, . - SOLUTION:
A truth assignment for
*U*. - MEASURE:
Number of clauses satisfied by the truth assignment.

*Good News:*Approximable within if every clause consists of exactly*k*literals [276].*Bad News:*APX-complete [393].*Comment:*MAXIMUM 3-SATISFIABILITY is approximable within 1.249 [453] and is approximable within 8/7 for satisfiable instances [291]. MAXIMUM*K*-SATISFIABILITY is not approximable within for any and , even if every clause consists of exactly*k*literals [242].MAXIMUM 2-SATISFIABILITY is approximable within 1.0741 [154], and is not approximable within 1.0476 [242]. The weighted version of this problem is as hard to approximate as the unweighted version [128]. If every clause consists of exactly

*k*literals, the weighted version of the problem is as hard to approximate as the unweighted version [128].Variation in which the number of occurrences of each variable is bounded by a constant

*B*for is still APX-complete [393] and [45]; for*B=6*it is not approximable within 1.0014 [76]. If every clause consists of exactly three literals and the number of occurrences of each variable is exactly 3, then the problem is polynomially solvable (see Problem 9.5.4 of [391]), but for exactly five occurrences, the problem is APX-complete [153].Admits a PTAS if [39]. Variation in which each clause is a Horn clause, i.e., contains at most one nonnegated variable, is APX-complete, even for

*k=2*[328].*Garey and Johnson:*LO2 and LO5