Next: MAXIMUM NUMBER OF SATISFIABLE
Up: Propositional Logic
Previous: MINIMUM DISTINGUISHED ONES
  Index
- INSTANCE:
Set U of variables, boolean expression F over U, a nonnegative bound
,
for each variable
a weight
such that
.
- SOLUTION:
A truth assignment for U, i.e., a subset
such that the
variables in U' are set to true and the variables in U-U' are set to false.
- MEASURE:
if the truth assignment satisfies
the boolean expression F and B otherwise.
- Good News:
Approximable within 2 [126].
- Bad News:
APX-complete [126].
- Comment:
Variation in which
is PTAS-complete [126].
Viggo Kann
2000-03-20