License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DFU.Vol7.15301.233
URN: urn:nbn:de:0030-drops-69665
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/6966/
Go to the corresponding DFU Volume Portal

Krokhin, Andrei ; Zivny, Stanislav

The Complexity of Valued CSPs

pdf-format:
DFU-Vol7-15301-9.pdf (0.7 MB)

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.

BibTeX - Entry

@InCollection{krokhin_et_al:DFU:2017:6966,
  author =	{Andrei Krokhin and Stanislav Zivny},
  title =	{{The Complexity of Valued CSPs}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{233--266},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Andrei Krokhin and Stanislav Zivny},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/6966},
  URN =		{urn:nbn:de:0030-drops-69665},
  doi =		{10.4230/DFU.Vol7.15301.233},
  annote =	{Keywords: Constraint satisfaction problems, Optimisation, Tractability}
}

Keywords: Constraint satisfaction problems, Optimisation, Tractability
Collection: The Constraint Satisfaction Problem: Complexity and Approximability
Issue Date: 2017
Date of publication: 21.02.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI