Professor Andrei Krokhin andrei.krokhin@durham.ac.uk
Professor
The complexity of Valued CSPs
Krokhin, A.; Živný, S.
Authors
S. Živný
Contributors
Professor Andrei Krokhin andrei.krokhin@durham.ac.uk
Editor
S. Živný
Editor
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.
Publication Date | Jan 1, 2017 |
---|---|
Deposit Date | Mar 9, 2017 |
Publicly Available Date | Mar 10, 2017 |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | 233-266 |
Series Title | Dagstuhl follow-ups |
Book Title | The constraint satisfaction problem : complexity and approximability. |
Chapter Number | 9 |
DOI | https://doi.org/10.4230/dfu.vol7.15301.9 |
Public URL | https://durham-repository.worktribe.com/output/1663754 |
Files
Published Book Chapter
(757 Kb)
PDF
Publisher Licence URL
http://creativecommons.org/licenses/by/4.0/
Copyright Statement
© Andrei Krokhin and Stanislav Živný; licensed under Creative Commons License BY
You might also like
Algebraic approach to promise constraint satisfaction
(2019)
Presentation / Conference Contribution
The complexity of 3-colouring H-colourable graphs
(2020)
Presentation / Conference Contribution
Robust algorithms with polynomial loss for near-unanimity CSPs
(2017)
Presentation / Conference Contribution
The Complexity of General-Valued CSPs
(2015)
Presentation / Conference Contribution
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search