Next: MAXIMUM K-CONSTRAINT SATISFACTION
Up: Propositional Logic
Previous: MINIMUM NUMBER OF SATISFIABLE
  Index
- INSTANCE:
Set U of variables, collection C of equivalences, i.e., pairs of literals
over U.
- SOLUTION:
A truth assignment for U.
- MEASURE:
Number of equivalences that are not satisfied by the truth assignment.
- Good News:
Approximable within
[177].
- Bad News:
APX-hard [177].
- Comment:
The complementary maximization problem is approximable within 1.138
[Kann, --].
Viggo Kann
1999-04-22