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

*Good News:*Approximable within [451].*Bad News:*APX-complete [77].*Comment:*Transformation from MAXIMUM 2-SATISFIABILITY. Approximable within 1.165 but not within 1.111 for*k=2*, and approximable within 2 but not within 2 for*k=3*. There are also results of specific variations of the problem for [477]. Not approximable within for large enough*k*[451]. Not in APX when [457]. When there are exactly*k*variables in each clause and the number of clauses is the problem admits a randomized PTAS [21]. A complete classification of the approximability of optimization problems derived from Boolean constraint satisfaction is contained in [309] (maximization) and in [308] (minimization).