2026-08-02T22:58:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6966 2024-03-06T10:28:04Z ddc:004 open_access

The Complexity of Valued CSPs Krokhin, Andrei Zivny, Stanislav Constraint satisfaction problems Optimisation Tractability 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrei Krokhin and Stanislav Zivny 2017 Is Part Of Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017) InCollection Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DFU.Vol7.15301.233 urn:nbn:de:0030-drops-69665 https://drops.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.233 eng https://creativecommons.org/licenses/by/3.0/legalcode