Next: MAXIMUM K-SATISFIABILITY Up: Propositional Logic Previous: Propositional Logic Index

### MAXIMUM SATISFIABILITY

- 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 [38].

- Bad News: APX-complete [371].

- 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 [38]. 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 [371]. Admits a PTAS for `planar' instances [289]. The corresponding minimization problem MINIMUM SATISFIABILITY is approximable within 2 [74] 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 [120] .

- Garey and Johnson: LO1

Next: MAXIMUM K-SATISFIABILITY Up: Propositional Logic Previous: Propositional Logic Index