The approximability of three-valued MAX CSP

Details The approximability of three-valued MAX CSP The approximability of three-valued MAX CSP

2004-12-10

arxiv.org/abs/cs/0412042v1

Computer Science

Computational Complexity

Scientific paper

In the maximum constraint satisfaction problem (Max CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given domain to the variables so as to maximize the number (or the total weight, for the weighted case) of satisfied constraints. This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. It is known that every Boolean (that is, two-valued) Max CSP problem with a finite set of allowed constraint types is either solvable exactly in polynomial time or else APX-complete (and hence can have no polynomial time approximation scheme unless P=NP. It has been an open problem for several years whether this result can be extended to non-Boolean Max CSP, which is much more difficult to analyze than the Boolean case. In this paper, we make the first step in this direction by establishing this result for Max CSP over a three-element domain. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description uses the well-known algebraic combinatorial property of supermodularity. We also show that every hard three-valued Max CSP problem contains, in a certain specified sense, one of the two basic hard Max CSP problems which are the Maximum k-colourable subgraph problems for k=2,3.

Affiliated with

Also associated with

No associations

Rating

The approximability of three-valued MAX CSP does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The approximability of three-valued MAX CSP, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The approximability of three-valued MAX CSP will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-451951