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.
Comment:
Transformation from MAXIMUM 2-SATISFIABILITY.
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].
The same variation admits a PTAS for k=2 if the number of occurrences of
each variable is
[66].
.
[80].
[66].