S. Khanna, M. Sudan, and Luca Trevisan.
Constraint Satisfaction: The Approximability of Minimization
Submitted, December 1996.
We study the approximability of minimization problems derived
from boolean constraint satisfaction. A problem in this
framework is characterized by a collection F of "constraints"
(i.e. boolean functions) and an instance of a problem is a set
of constraints drawn from F applied to subsets of n
boolean variables. We study two natural minimization problems
associated to F: in MINCSP(F) we search for an assigment
of values to the variables that contradicts the minimum number of
constraints. In MINONES(F) 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 F
the approximability of MINCSP(F) and MINONES(F) is
completely determined by the partition containing F.