We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

The complexity of valued CSPs.

Krokhin, A. and Živný, S. (2017) 'The complexity of valued CSPs.', in The constraint satisfaction problem : complexity and approximability. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 233-266. Dagstuhl follow-ups. (7).


We survey recent results on the broad family of problems that can be cast as valued constraint satisfaction problems (VCSPs). We discuss general methods for analysing the complexity of such problems, give examples of tractable cases, and identify general features of the complexity landscape.

Item Type:Book chapter
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
Publisher Web site:
Publisher statement:© Andrei Krokhin and Stanislav Živný; licensed under Creative Commons License BY
Date accepted:No date available
Date deposited:10 March 2017
Date of first online publication:2017
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar