__
TR96-062 | 3rd December 1996 00:00
__

#### A Complete Characterization of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction

**Abstract:**

In this paper we study the approximability of boolean constraint

satisfaction problems. A problem in this class consists of some

collection of ``constraints'' (i.e., functions

$f:\{0,1\}^k \rightarrow \{0,1\}$); an instance of a problem is a set

of constraints applied to specified subsets of $n$ boolean

variables. Schaefer earlier studied the question of whether one

could find in polynomial time a setting of the variables satisfying

all constraints; he showed that every such problem is either in P

or is NP-complete. We consider optimization variants of these

problems in which one either tries to maximize the number of

satisfied constraints (as in MAX 3SAT or MAX CUT) or tries to

find an assignment satisfying all constraints which maximizes the

number of variables set to 1 (as in MAX CUT or MAX CLIQUE). We

completely classify the approximability of all such problems.

In the first case, we show that any such optimization problem

is either in P or is MAX SNP-hard. In the second case, we

show that such problems fall precisely into one of five classes:

solvable in polynomial-time, approximable to within constant factors

in polynomial time (but no better), approximable to within polynomial

factors in polynomial time (but no better), not approximable to within

any factor but decidable in polynomial time, and not decidable in

polynomial time (unless P = NP). This result proves formally for this

class of problems two results which to this point have only

been empirical observations; namely, that NP-hard problems in

MAX SNP always turn out to be MAX SNP-hard, and that there seem

to be no natural maximization problems approximable to within

polylogarithmic factors but no better.