LO2 M AXIMUM K -S ATISFIABILITY

     
• I NSTANCE : 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, .
• S OLUTION : A truth assignment for U .
• M EASURE : Number of clauses satisfied by the truth assignment.

• Good News: Approximable within if every clause consists of exactly k literals [ 194 ].
• Bad News: A PX -complete [ 284 ].
• Comment: M AXIMUM 3-S ATISFIABILITY is approximable within 1.249 [ 333 ]. M AXIMUM K -S ATISFIABILITY is not approximable within for any and , even if every clause consists of exactly k literals [ 164 ].  

  M AXIMUM 2-S ATISFIABILITY is approximable within 1.0741 [ 104 ], and is not approximable within 1.0476 [ 164 ].   Variation in which the number of occurrences of any literal is bounded by a constant B for is still A PX -complete [ 284 ]. Admits a PTAS if [ 24 ]. Variation in which each clause is a Horn clause, i.e., contains at most one nonnegated variable, is A PX -complete, even for k=2 [ 237 ].    

• Garey and Johnson: LO2 and LO5