S. Khanna, M. Sudan, and Luca Trevisan.<br>
<b>Constraint Satisfaction: The Approximability of Minimization
Problems.</b><br>
Submitted, December 1996.<br>

<dl>

<dt> <b> Abstract</b> <dd>
We study the approximability of minimization problems derived
from boolean constraint satisfaction. A problem in this
framework is characterized by a collection  <b>F</b> of "constraints"
(i.e. boolean functions) and an instance of a problem is a set
of constraints drawn from <b>F</b> applied to subsets of n
boolean variables. We study two natural minimization problems
associated to <b>F</b>: in  MINCSP(<b>F</b>) we search for an assigment
of values to the variables that contradicts the minimum number of
constraints. In MINONES(<b>F</b>) the goal is to find an assignment
satisfying all constraints and with a minimum number of ones.
Our main result is that there exists a finite partition of
the space of constraint sets such that, for any given <b>F</b>
the approximability of MINCSP(<b>F</b>) and MINONES(<b>F</b>) is
completely determined by the partition containing <b>F</b>. 
</dl>