License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagRep.2.11.1
URN: urn:nbn:de:0030-drops-39764
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/3976/
Go back to Dagstuhl Reports

Hastad, Johan ; Krokhin, Andrei ; Marx, Dániel
Weitere Beteiligte (Hrsg. etc.): Johan Hastad and Andrei Krokhin and Dániel Marx

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

pdf-format:
dagrep_v002_i011_p001_s12451.pdf (0.8 MB)

Abstract

During the past two decades, an impressive array of diverse methods from several different mathematical fields, including algebra, logic, analysis, 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. The Dagstuhl Seminar 12451 ``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. This report documents the material presented during the course of the seminar.

BibTeX - Entry

@Article{hastad_et_al:DR:2013:3976,
  author =	{Johan Hastad and Andrei Krokhin and D{\'a}niel Marx},
  title =	{{The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 12451)}},
  pages =	{1--19},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{11},
  editor =	{Johan Hastad 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/2013/3976},
  URN =		{urn:nbn:de:0030-drops-39764},
  doi =		{10.4230/DagRep.2.11.1},
  annote =	{Keywords: Constraint satisfaction problem (CSP); Computational complexity; CSP dichotomy conjecture; Hardness of approximation; Unique games conjceture; }
}

Keywords: Constraint satisfaction problem (CSP); Computational complexity; CSP dichotomy conjecture; Hardness of approximation; Unique games conjceture;
Freie Schlagwörter (englisch): Fixed-parameter tractability; Descriptive complexity; niversal algebra; Logic; Decomposition methods
Collection: Dagstuhl Reports, Volume 2, Issue 11
Issue Date: 2013
Date of publication: 14.03.2013

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