MAXIMUM NOT-ALL-EQUAL 3-SATISFIABILITY

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

• SOLUTION: A truth assignment for U and a subset $C'\subseteq C$ of the clauses such that each clause in C' has at least one true literal and at least one false literal.

• MEASURE: $\vert C'\vert$.

  
  

• Good News: Approximable within 1.138 [287].

• Bad News: APX-complete [393]. Not approximable within 1.090 [477].

• Comment: Transformation from MAXIMUM 2-SATISFIABILITY. Approximable within 1.096 for satisfiable instances [477]. MAXIMUM NOT-ALL-EQUAL SATISFYABILITY, without restrictions on the number of literals in a clause, is approximable within 1.380 [20].

• Garey and Johnson: LO3