Next: MINIMUM 3DNF SATISFIABILITY
Up: Propositional Logic
Previous: MINIMUM K-SATISFIABILITY
  Index
- INSTANCE:
Set U of variables, collection C of disjunctive clauses of at most
3 literals, where a literal is a variable or a negated variable in U.
- SOLUTION:
A truth assignment for U and a subset
of the clauses such
that each clause in C' has at least one true literal and at least one
false literal.
- MEASURE:
|C'|.
- Good News:
Approximable within 1.138 [272].
- Bad News:
APX-complete [371].
Not approximable within 1.090 [453].
- Comment:
Transformation from MAXIMUM 2-SATISFIABILITY.
Approximable within 1.096 for satisfiable instances [453].
MAXIMUM NOT-ALL-EQUAL SATISFYABILITY, without restrictions on
the number of literals in a clause, is approximable within 1.380
[19].
- Garey and Johnson: LO3
Viggo Kann
1999-04-22