Next: MAXIMUM K-SATISFIABILITY
Up: Propositional Logic
Previous: Propositional Logic
Index
- INSTANCE:
Set U of variables, collection C of disjunctive clauses of literals,
where a literal is a variable or a negated variable in U.
- SOLUTION:
A truth assignment for U.
- MEASURE:
Number of clauses satisfied by the truth assignment.
- Good News:
Approximable within 1.2987 [41].
- Bad News:
APX-complete [393].
- Comment:
Variation in which each clause has a nonnegative weight and the
objective is to maximize the total weight of the satisfied clauses is
also approximable within 1.2987 [41].
Generalization in which each clause is a disjunction of conjunctions of
literals and each conjunction consists of at most k literals, where k
is a positive constant, is still APX-complete
[393].
Admits a PTAS for `planar' instances [304].
The corresponding minimization problem MINIMUM SATISFIABILITY is approximable within
2 [80] and its variation in which each clause has a
nonnegative weight and the objective is to minimize the total weight
of the satisfied clauses is as hard to approximate as the unweighted
version [128].
- Garey and Johnson: LO1
Next: MAXIMUM K-SATISFIABILITY
Up: Propositional Logic
Previous: Propositional Logic
Index
Viggo Kann
2000-03-20