This paper continues the work initiated by Creignou [Cre95] and
Khanna, Sudan and Williamson [KSW96] who classify maximization
problems derived from boolean constraint satisfaction. Here we
study the approximability of {\em minimization} problems derived
thence. A problem in this framework is characterized by a
collection F of "constraints" (i.e., functions f:{0,1}^k -> {0,1})
and an instance of a problem is constraints drawn from F applied
to specified subsets of n boolean variables. We study the two
minimization analogs of classes studied in [KSW96]: in one variant,
namely Min CSP(F), the objective is to find an assignment to
minimize the number of unsatisfied constraints, while in the other,
namely Min Ones(F), the goal is to find a satisfying assignment with
minimum number of ones. These two classes together capture an entire
spectrum of important minimization problems including $s$-$t$ Min Cut,
vertex cover, hitting set with bounded size sets, integer programs
with two variables per inequality, deleting minimum number of edges
to make a graph bipartite, deleting minimum number of clauses to
make a 2CNF formula satisfiable, and nearest codeword. Our main result
is that there exists a finite partition of the space of all constraint
sets such that for any given family F, the approximability of
Min CSP(F) and Min Ones(F) is completely determined by the partition
containing it. Furthermore we present a compact set of rules which,
given F, determine which partition contains it. On the one hand, our
classification underscores central elements governing the
approximability of problems in these classes, while on the other
hand, it unifies a large number of algorithmic and hardness of
approximation results. When contrasted with the work of [KSW96],
our results serve to formally highlight inherent differences
between maximization and minization problems.