Next:
LO12 MAXIMUM K-CONSTRAINT
Up:
Propositional Logic
Previous:
LO10 MINIMUM NUMBER
-
I
NSTANCE
:
Set
U
of variables, collection
C
of equivalences, i.e., pairs of literals
over
U
.
-
S
OLUTION
:
A truth assignment for
U
.
-
M
EASURE
:
Number of equivalences that are not satisfied by the truth assignment.
-
Good News:
Approximable within
[
128
].
-
Bad News:
A
PX
-hard [
128
].
-
Comment:
The complementary maximization problem is approximable within 1.138
[Kann, --].
Viggo Kann
Mon Apr 21 13:07:14 MET DST 1997