Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Bulatov, Andrei A.; Guruswami, Venkatesan; Krokhin, Andrei; Marx, Dániel http://www.dagstuhl.de/dagrep License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-56714
URL:

; ; ;
Weitere Beteiligte (Hrsg. etc.): Andrei A. Bulatov and Venkatesan Guruswami and Andrei Krokhin and Dániel Marx

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301)

pdf-format:


Abstract

During the past two decades, an impressive array of diverse methods from several different mathematical fields, including algebra, logic, mathematical programming, probability theory, graph theory, and combinatorics, have been used to analyze both the computational complexity and approximabilty of algorithmic tasks related to the constraint satisfaction problem (CSP), as well as the applicability/limitations of algorithmic techniques. This research direction develops at an impressive speed, regularly producing very strong and general results. The Dagstuhl Seminar 15301 "The Constraint Satisfaction Problem: Complexity and Approximability" was aimed at bringing together researchers using all the different techniques in the study of the CSP, so that they can share their insights obtained during the past three years. This report documents the material presented during the course of the seminar.

BibTeX - Entry

@Article{bulatov_et_al:DR:2016:5671,
  author =	{Andrei A. Bulatov and Venkatesan Guruswami and Andrei Krokhin and D{\'a}niel Marx},
  title =	{{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 15301)}},
  pages =	{22--41},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{5},
  number =	{7},
  editor =	{Andrei A. Bulatov and Venkatesan Guruswami and Andrei Krokhin and D{\'a}niel Marx},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5671},
  URN =		{urn:nbn:de:0030-drops-56714},
  doi =		{10.4230/DagRep.5.7.22},
  annote =	{Keywords: Constraint satisfaction problem (CSP), Computational complexity, CSP dichotomy conjecture, Hardness of approximation, Unique games conjecture, }
}

Keywords: Constraint satisfaction problem (CSP), Computational complexity, CSP dichotomy conjecture, Hardness of approximation, Unique games conjecture,
Freie Schlagwörter (englisch): Fixed-parameter tractability, Descriptive complexity, Universal algebra, Logic, Decomposition methods
Seminar: Dagstuhl Reports, Volume 5, Issue 7
Issue date: 2016
Date of publication: 2016


DROPS-Home | Fulltext Search | Imprint Published by LZI