MINIMUM EQUIVALENCE DELETION

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 $O(\log\vert U\vert)$ [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 $\Theta(\vert U\vert)$ [66].

Viggo Kann
2000-03-20