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, $k\ge 2$.

• 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 [276].

• Bad News: APX-complete [393].

• Comment: MAXIMUM 3-SATISFIABILITY is approximable within 1.249 [453] and is approximable within 8/7 for satisfiable instances [291]. MAXIMUM K-SATISFIABILITY is not approximable within $1/(1-2^{-k})-\varepsilon$ for any $\varepsilon >0$ and $k\ge 3$, even if every clause consists of exactly k literals [242].

  MAXIMUM 2-SATISFIABILITY is approximable within 1.0741 [154], and is not approximable within 1.0476 [242]. The weighted version of this problem is as hard to approximate as the unweighted version [128]. If every clause consists of exactly k literals, the weighted version of the problem is as hard to approximate as the unweighted version [128].

  Variation in which the number of occurrences of each variable is bounded by a constant B for $B \ge 3$ is still APX-complete [393] and [45]; for B=6 it is not approximable within 1.0014 [76]. If every clause consists of exactly three literals and the number of occurrences of each variable is exactly 3, then the problem is polynomially solvable (see Problem 9.5.4 of [391]), but for exactly five occurrences, the problem is APX-complete [153].

  Admits a PTAS if $\vert C\vert=\Theta(\vert U\vert^k)$ [39]. Variation in which each clause is a Horn clause, i.e., contains at most one nonnegated variable, is APX-complete, even for k=2 [328].

• Garey and Johnson: LO2 and LO5