We study optimization problems that may be expressed as Boolean constraint
satisfaction problems. An instance of a Boolean constraint satisfaction pro
blem is given by m constraints applied to n Boolean variables. Different co
mputational problems arise from constraint satisfaction problems depending
on the nature of the underlying constraints as well as on the goal of the o
ptimization task. Here we consider four possible goals: Max CSP (Min CSP) i
s the class of problems where the goal is to nd an assignment maximizing th
e number of satis ed constraints (minimizing the number of unsatisfied cons
traints). Max Ones (Min Ones) is the class of optimization problems where t
he goal is to nd an assignment satisfying all constraints with maximum (min
imum) number of variables set to 1. Each class consists of infinitely many
problems and a problem within a class is specified by a finite collection o
f finite Boolean functions that describe the possible constraints that may
be used.
Tight bounds on the approximability of every problem in Max CSP were obtain
ed by Creignou [J. Comput. System Sci., 51 (1995), pp. 511-522]. In this wo
rk we determine tight bounds on the approximability (i.e., the ratio to wit
hin which each problem may be approximated in polynomial time) of every pro
blem in Max Ones, Min CSP, and Min Ones. Combined with the result of Creign
ou, this completely classifies all optimization problems derived from Boole
an constraint satisfaction. Our results capture a diverse collection of opt
imization problems such as MAX 3-SAT, Max Cut, Max Clique, Min Cut, Nearest
Codeword, etc. Our results unify recent results on the (in-) approximabili
ty of these optimization problems and yield a compact presentation of most
known results. Moreover, these results provide a formal basis to many state
ments on the behavior of natural optimization problems that have so far bee
n observed only empirically.