Next: MAXIMUM WEIGHTED SATISFIABILITY WITH
Up: Propositional Logic
Previous: MAXIMUM DISTINGUISHED ONES
  Index
- INSTANCE:
Disjoint sets X,Z of variables, collection C of disjunctive clauses of
at most 3 literals, where a literal is a variable or a negated variable in
.
- SOLUTION:
Truth assignment for X and Z that satisfies every clause in C.
- MEASURE:
The number of Z variables that are set to true in the assignment.
- Bad News:
NPO PB-complete [284].
- Comment:
Transformation from MINIMUM INDEPENDENT DOMINATING SET.
Not approximable within
for any
[279].
MINIMUM ONES, the variation in which all variables are distinguished, i.e.
,
is also NPO PB-complete [284], and is not
approximable within
for any
[279].
MINIMUM ONES for clauses of 2 literals is approximable within 2 [210].
MINIMUM WEIGHTED SATISFIABILITY, the weighted version, in which every variable is assigned
a nonnegative weight, is NPO-complete [388].
Variations corresponding to three- and four-valued logics have also been
considered [145].
Viggo Kann
2000-03-20