Approximate constraint satisfaction
Lars Fredrik Engebretsen · 2000
In this thesis we study optimization versions of NP-complete constraint satisfaction problems. An example of such a problem is the Maximum Satisfiability problem. An instance of this problem consists of clauses formed by Boolean variables and the goal is to find an assignment to the variables that satisfies as many clauses as possible. Since it is NP-complete to decide if all clauses are simultaneously satisfiable, the Maximum Satisfiability problem cannot be solved exactly in polynomial time unless P = NP. However, it may be possible to solve the problem approximately, in the sense that the number of satisfied clauses is at most some factor c from the optimum. Such an algorithm is called a c-approximation algorithm. The foundation of the results presented in this thesis is the approximability of several constraint satisfaction problems. We provide both upper and lower bounds on the approximability. A proof of an upper bound is usually a polynomial time c-approximation algorithm for so...