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).
Abstract
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 (740Kb) |
| Status: | Peer-reviewed |
| Publisher Web site: | https://doi.org/10.4230/DFU.Vol7.15301.9 |
| 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
| Export: | |
| Look up in GoogleScholar |
