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
[189].
- Bad News:
APX-hard [189].
- Comment:
The complementary maximization problem is approximable within 1.138
[Kann, --]. It admits a PTAS if the number of occurrences of each variable
is
[66].
Viggo Kann
2000-03-20