Computer Science – Computational Complexity
Scientific paper
2010-08-18
Computer Science
Computational Complexity
14 pages
Scientific paper
We study optimisation problems that can be formulated as valued constraint satisfaction problems (VCSP). A problem from VCSP is characterised by a \emph{constraint language}, a fixed set of cost functions taking finite and infinite costs over a finite domain. An instance of the problem is specified by a sum of cost functions from the language and the goal is to minimise the sum. We are interested in \emph{tractable} constraint languages; that is, languages that give rise to VCSP instances solvable in polynomial time. Cohen et al. (AIJ'06) have shown that constraint languages that admit the MJN multimorphism are tractable. Moreover, using a minimisation algorithm for submodular functions, Cohen et al. (TCS'08) have shown that constraint languages that admit an STP (symmetric tournament pair) multimorphism are tractable. We generalise these results by showing that languages admitting the MJN multimorphism on a subdomain and an STP multimorphisms on the complement of the subdomain are tractable. The algorithm is a reduction to the algorithm for languages admitting an STP multimorphism.
Kolmogorov Vladimir
Zivny Stanislav
No associations
LandOfFree
Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms 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 Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalising tractable VCSPs defined by symmetric tournament pair multimorphisms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-506611