MAXIMUM K-CONSTRAINT SATISFACTION

• INSTANCE: Set U of variables, collection C of conjunctive clauses of at most k literals, where a literal is a variable or a negated variable in U, and 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 $2^{k-1}$ [451].

• Bad News: APX-complete [77].

• Comment: Transformation from MAXIMUM 2-SATISFIABILITY. Approximable within 1.165 but not within 1.111 for k=2, and approximable within 2 but not within 2$-\varepsilon$ for k=3. There are also results of specific variations of the problem for $k\le 3$ [477]. Not approximable within $2^{0.09k}$ for large enough k [451]. Not in APX when $k=\log\vert C\vert$ [457]. When there are exactly k variables in each clause and the number of clauses is $\Theta(\vert U\vert^k)$ the problem admits a randomized PTAS [21]. A complete classification of the approximability of optimization problems derived from Boolean constraint satisfaction is contained in [309] (maximization) and in [308] (minimization).