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, .
SOLUTION:
A truth assignment for U.
MEASURE:
Number of clauses satisfied by the truth assignment.
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
for k=3.
There are also results of specific variations of the problem
for
[477].
Not approximable within
for large enough k
[451].
Not in APX when
[457].
When there are exactly k variables in each clause and the number of
clauses is
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).
.
[451].
for k=3.
There are also results of specific variations of the problem
for 
[477].
Not approximable within 
for large enough k
[451].
Not in APX when 
[457].
When there are exactly k variables in each clause and the number of
clauses is 
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).