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

### MAXIMUM K-SATISFIABILITY

- INSTANCE: Set U of variables, collection C of disjunctive clauses of at most k literals, where a literal is a variable or a negated variable in U. k is a constant, .

- SOLUTION: A truth assignment for U.

- MEASURE: Number of clauses satisfied by the truth assignment.

- Good News: Approximable within 1/(1-2-k) if every clause consists of exactly k literals [261].

- Bad News: APX-complete [371].

- Comment: MAXIMUM 3-SATISFIABILITY is approximable within 1.249 [430] and is approximable within 8/7 for satisfiable instances [276]. MAXIMUM K-SATISFIABILITY is not approximable within for any and , even if every clause consists of exactly k literals [226].

  MAXIMUM 2-SATISFIABILITY is approximable within 1.0741 [143], and is not approximable within 1.0476 [226]. The weighted version of this problem is as hard to approximate as the unweighted version [120].

  If every clause consists of exactly k literals, the weighted version of the problem is as hard to approximate as the unweighted version [120]. Variation in which the number of occurrences of any literal is bounded by a constant B for is still APX-complete [371] and [42]; for B=6 it is not approximable within 1.0014 [70].

  Admits a PTAS if [37]. Variation in which each clause is a Horn clause, i.e., contains at most one nonnegated variable, is APX-complete, even for k=2 [311].

- Garey and Johnson: LO2 and LO5

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