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:
.
- Good News:
Approximable within 1.138 [287].
- Bad News:
APX-complete [393].
Not approximable within 1.090 [477].
- Comment:
Transformation from MAXIMUM 2-SATISFIABILITY.
Approximable within 1.096 for satisfiable instances [477].
MAXIMUM NOT-ALL-EQUAL SATISFYABILITY, without restrictions on
the number of literals in a clause, is approximable within 1.380
[20].
- Garey and Johnson: LO3
Viggo Kann
2000-03-20