TR96-064 Authors: Sanjeev Khanna, Madhu Sudan, Luca Trevisan

Publication: 13th December 1996 10:05

Downloads: 1692

Keywords:

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.