Computer Science – Computational Complexity
Scientific paper
2011-10-13
Computer Science
Computational Complexity
Scientific paper
Maximum surjective constraint satisfaction problems (Max-Sur-CSPs) are computational problems where we are given a set of variables denoting values from a finite domain B and a set of constraints on the variables. A solution to such a problem is a surjective mapping from the set of variables to B such that the number of satisfied constraints is maximized. We study the approximation performance that can be acccchieved by algorithms for these problems, mainly by investigating their relation with Max-CSPs (which are the corresponding problems without the surjectivity requirement). Our work gives a complexity dichotomy for Max-Sur-CSP(B) between PTAS and APX-complete, under the assumption that there is a complexity dichotomy for Max-CSP(B) between PO and APX-complete, which has already been proved on the Boolean domain and 3-element domains.
Bach Walter
Zhou Hang
No associations
LandOfFree
Approximation for Maximum Surjective Constraint Satisfaction Problems 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 Approximation for Maximum Surjective Constraint Satisfaction Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation for Maximum Surjective Constraint Satisfaction Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-500450