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