S. Khanna, M. Sudan, and Luca Trevisan.
Constraint Satisfaction: The Approximability of Minimization Problems.
Submitted, December 1996.
Abstract
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.