The complexity of Valued CSPs

Krokhin, A.; Živný, S.

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.

Citation

Krokhin, A., & Živný, S. (2017). The complexity of Valued CSPs. In A. Krokhin, & S. Živný (Eds.), The constraint satisfaction problem : complexity and approximability (233-266). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/dfu.vol7.15301.9

• 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