P. Jeavons
The Complexity of Valued Constraint Satisfaction
Jeavons, P.; Krokhin, A.; Živný, S.
Abstract
We survey recent results on the broad family of problems that can be cast as valued constraint satisfaction problems. We discuss general methods for analysing the complexity of such problems, give examples of tractable cases, and identify general features of the complexity landscape.
Citation
Jeavons, P., Krokhin, A., & Živný, S. (2014). The Complexity of Valued Constraint Satisfaction. Bulletin of the European Association for Theoretical Computer Science, 113, 21-55
Journal Article Type | Article |
---|---|
Publication Date | Jun 1, 2014 |
Deposit Date | Oct 16, 2014 |
Publicly Available Date | Oct 20, 2014 |
Journal | Bulletin of the European Association for Theoretical Computer Science. |
Print ISSN | 0252-9742 |
Publisher | European Association for Theoretical Computer Science |
Peer Reviewed | Not Peer Reviewed |
Volume | 113 |
Pages | 21-55 |
Public URL | https://durham-repository.worktribe.com/output/1419157 |
Publisher URL | http://bulletin.eatcs.org/index.php/beatcs/article/view/266 |
Files
Published Journal Article
(315 Kb)
PDF
You might also like
Topology and adjunction in promise constraint satisfaction
(2023)
Journal Article
Algebraic Approach to Promise Constraint Satisfaction
(2021)
Journal Article
The complexity of 3-colouring H-colourable graphs
(2020)
Presentation / Conference Contribution
Robust algorithms with polynomial loss for near-unanimity CSPs
(2019)
Journal Article
Algebraic approach to promise constraint satisfaction
(2019)
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