Next: MAXIMUM NOT-ALL-EQUAL 3-SATISFIABILITY
Up: Propositional Logic
Previous: MAXIMUM K-SATISFIABILITY
  Index
- 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
[80].
- Bad News:
APX-complete for every
[328].
- 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].
- Garey and Johnson: LO2
Viggo Kann
2000-03-20