DFU.Vol7.15301.233.pdf
- Filesize: 0.72 MB
- 34 pages
Document
The Complexity of Valued CSPs
Authors
-
Part of:
Volume:
The Constraint Satisfaction Problem: Complexity and Approximability (DFU - Vol. 7)
Series: Dagstuhl Follow-Ups (DFU) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-02-21
Cite AsGet BibTex
Andrei Krokhin and Stanislav Zivny. The Complexity of Valued CSPs. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 233-266, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/DFU.Vol7.15301.233
https://doi.org/10.4230/DFU.Vol7.15301.233
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.
Keywords
- Constraint satisfaction problems
- Optimisation
- Tractability
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads