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 [269].
- Comment:
Transformation from MINIMUM INDEPENDENT DOMINATING SET.
Not approximable within
for any
[264].
MINIMUM ONES, the variation in which all variables are distinguished, i.e.
,
is also NPO PB-complete [269], and is not
approximable within
for any
[264].
MINIMUM ONES for clauses of 2 literals is approximable within 2 [197].
MINIMUM WEIGHTED SATISFIABILITY, the weighted version, in which every variable is assigned
a nonnegative weight, is NPO-complete [367].
Variations corresponding to three- and four-valued logics have also been
considered [134].
Viggo Kann
1999-04-22