Constraint satisfaction: The approximability of minimization problems

Abstract

This paper continues the work initiated by N. Creignou (1995) and S. Khanna et al. (1997) who classify maximization problems derived from Boolean constraint satisfaction. We study the approximability of minimization problems derived thence. A problem in this framework is characterized by a collection F of »constraints» (i.e., functions f: {0,1}krarr/{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 by S. Khanna et al.: 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 graph bipartization, clause deletion in CNF formulae, 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 F, the approximability of MIN CSP (F) and MIN ONES (F) is completely determined by the partition containing it. Moreover we present a compact set of rules that determines which partition contains a given family F. Our classification identifies the central elements governing the approximability of problems in these classes, by unifying a large collection algorithmic and hardness of approximation results.