The Complexity of Valued Constraint Satisfaction

Jeavons, P.; Krokhin, A.; Živný, S.

The Complexity of Valued Constraint Satisfaction

Jeavons, P.; Krokhin, A.; Živný, S.

Authors

P. Jeavons

Professor Andrei Krokhin andrei.krokhin@durham.ac.uk
Professor

S. Živný

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
Publisher URL	http://bulletin.eatcs.org/index.php/beatcs/article/view/266