24 Search Results for "Krokhin, Andrei"


Volume

Dagstuhl Follow-Ups, Volume 7

The Constraint Satisfaction Problem: Complexity and Approximability

Editors: Andrei Krokhin and Stanislav Zivny

Document
Track A: Algorithms, Complexity and Games
Conditional Dichotomy of Boolean Ordered Promise CSPs

Authors: Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
Promise Constraint Satisfaction Problems (PCSPs) are a generalization of Constraint Satisfaction Problems (CSPs) where each predicate has a strong and a weak form and given a CSP instance, the objective is to distinguish if the strong form can be satisfied vs. even the weak form cannot be satisfied. Since their formal introduction by Austrin, Guruswami, and Håstad [Per Austrin et al., 2017], there has been a flurry of works on PCSPs, including recent breakthroughs in approximate graph coloring [Barto et al., 2018; Andrei A. Krokhin and Jakub Opršal, 2019; Marcin Wrochna and Stanislav Zivný, 2020]. The key tool in studying PCSPs is the algebraic framework developed in the context of CSPs where the closure properties of the satisfying solutions known as polymorphisms are analyzed. The polymorphisms of PCSPs are significantly richer than CSPs - even in the Boolean case, we still do not know if there exists a dichotomy result for PCSPs analogous to Schaefer’s dichotomy result [Thomas J. Schaefer, 1978] for CSPs. In this paper, we study a special case of Boolean PCSPs, namely Boolean Ordered PCSPs where the Boolean PCSPs have the predicate x ≤ y. In the algebraic framework, this is the special case of Boolean PCSPs when the polymorphisms are monotone functions. We prove that Boolean Ordered PCSPs exhibit a computational dichotomy assuming the Rich 2-to-1 Conjecture [Mark Braverman et al., 2021] which is a perfect completeness surrogate of the Unique Games Conjecture. In particular, assuming the Rich 2-to-1 Conjecture, we prove that a Boolean Ordered PCSP can be solved in polynomial time if for every ε > 0, it has polymorphisms where each coordinate has Shapley value at most ε, else it is NP-hard. The algorithmic part of our dichotomy result is based on a structural lemma showing that Boolean monotone functions with each coordinate having low Shapley value have arbitrarily large threshold functions as minors. The hardness part proceeds by showing that the Shapley value is consistent under a uniformly random 2-to-1 minor. As a structural result of independent interest, we construct an example to show that the Shapley value can be inconsistent under an adversarial 2-to-1 minor.

Cite as

Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. Conditional Dichotomy of Boolean Ordered Promise CSPs. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{brakensiek_et_al:LIPIcs.ICALP.2021.37,
  author =	{Brakensiek, Joshua and Guruswami, Venkatesan and Sandeep, Sai},
  title =	{{Conditional Dichotomy of Boolean Ordered Promise CSPs}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.37},
  URN =		{urn:nbn:de:0030-drops-141060},
  doi =		{10.4230/LIPIcs.ICALP.2021.37},
  annote =	{Keywords: promise constraint satisfaction, Boolean ordered PCSP, Shapley value, rich 2-to-1 conjecture, random minor}
}
Document
Complete Volume
DFU, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability, Complete Volume

Authors: Andrei Krokhin and Stanislav Zivny

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


Abstract
DFU, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability, Complete Volume

Cite as

The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@Collection{DFU.Vol7.15301,
  title =	{{DFU, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability, Complete Volume}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301},
  URN =		{urn:nbn:de:0030-drops-69752},
  doi =		{10.4230/DFU.Vol7.15301},
  annote =	{Keywords: Nonnumerical Algorithms and Problems}
}
Document
Front Matter, Table of Contents, Preface, List of Authors

Authors: Andrei Krokhin and Stanislav Zivny

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


Abstract
Front Matter, Table of Contents, Preface, List of Authors

Cite as

The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 0:i-0:xii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InCollection{krokhin_et_al:DFU.Vol7.15301.i,
  author =	{Krokhin, Andrei and Zivny, Stanislav},
  title =	{{Front Matter, Table of Contents, Preface, List of Authors}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{0:i--0:xii},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.i},
  URN =		{urn:nbn:de:0030-drops-69702},
  doi =		{10.4230/DFU.Vol7.15301.i},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, List of Authors}
}
Document
Polymorphisms, and How to Use Them

Authors: Libor Barto, Andrei Krokhin, and Ross Willard

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


Abstract
This article describes the algebraic approach to Constraint Satisfaction Problem that led to many developments in both CSP and universal algebra. No prior knowledge of universal algebra is assumed.

Cite as

Libor Barto, Andrei Krokhin, and Ross Willard. Polymorphisms, and How to Use Them. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 1-44, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InCollection{barto_et_al:DFU.Vol7.15301.1,
  author =	{Barto, Libor and Krokhin, Andrei and Willard, Ross},
  title =	{{Polymorphisms, and How to Use Them}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{1--44},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.1},
  URN =		{urn:nbn:de:0030-drops-69595},
  doi =		{10.4230/DFU.Vol7.15301.1},
  annote =	{Keywords: Constraint satisfaction, Complexity, Universal algebra, Polymorphism}
}
Document
Absorption in Universal Algebra and CSP

Authors: Libor Barto and Marcin Kozik

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


Abstract
The algebraic approach to Constraint Satisfaction Problem led to many developments in both CSP and universal algebra. The notion of absorption was successfully applied on both sides of the connection. This article introduces the concept of absorption, illustrates its use in a number of basic proofs and provides an overview of the most important results obtained by using it.

Cite as

Libor Barto and Marcin Kozik. Absorption in Universal Algebra and CSP. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 45-77, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InCollection{barto_et_al:DFU.Vol7.15301.45,
  author =	{Barto, Libor and Kozik, Marcin},
  title =	{{Absorption in Universal Algebra and CSP}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{45--77},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.45},
  URN =		{urn:nbn:de:0030-drops-69608},
  doi =		{10.4230/DFU.Vol7.15301.45},
  annote =	{Keywords: Constraint satisfaction problem, Algebraic approach, Absorption}
}
Document
Constraint Satisfaction Problems over Numeric Domains

Authors: Manuel Bodirsky and Marcello Mamino

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


Abstract
We present a survey of complexity results for constraint satisfaction problems (CSPs) over the integers, the rationals, the reals, and the complex numbers. Examples of such problems are feasibility of linear programs, integer linear programming, the max-atoms problem, Hilbert's tenth problem, and many more. Our particular focus is to identify those CSPs that can be solved in polynomial time, and to distinguish them from CSPs that are NP-hard. A very helpful tool for obtaining complexity classifications in this context is the concept of a polymorphism from universal algebra.

Cite as

Manuel Bodirsky and Marcello Mamino. Constraint Satisfaction Problems over Numeric Domains. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 79-111, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InCollection{bodirsky_et_al:DFU.Vol7.15301.79,
  author =	{Bodirsky, Manuel and Mamino, Marcello},
  title =	{{Constraint Satisfaction Problems over Numeric Domains}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{79--111},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.79},
  URN =		{urn:nbn:de:0030-drops-69580},
  doi =		{10.4230/DFU.Vol7.15301.79},
  annote =	{Keywords: Constraint satisfaction problems, Numerical domains}
}
Document
Hybrid Tractable Classes of Constraint Problems

Authors: Martin C. Cooper and Stanislav Zivny

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


Abstract
We present a survey of complexity results for hybrid constraint satisfaction problems (CSPs) and valued constraint satisfaction problems (VCSPs). These are classes of (V)CSPs defined by restrictions that are not exclusively language-based or structure-based.

Cite as

Martin C. Cooper and Stanislav Zivny. Hybrid Tractable Classes of Constraint Problems. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 113-135, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InCollection{cooper_et_al:DFU.Vol7.15301.113,
  author =	{Cooper, Martin C. and Zivny, Stanislav},
  title =	{{Hybrid Tractable Classes of Constraint Problems}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{113--135},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.113},
  URN =		{urn:nbn:de:0030-drops-69616},
  doi =		{10.4230/DFU.Vol7.15301.113},
  annote =	{Keywords: Constraint satisfaction problems, Optimisation, Tractability}
}
Document
Backdoor Sets for CSP

Authors: Serge Gaspers, Sebastian Ordyniak, and Stefan Szeider

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


Abstract
A backdoor set of a CSP instance is a set of variables whose instantiation moves the instance into a fixed class of tractable instances (an island of tractability). An interesting algorithmic task is to find a small backdoor set efficiently: once it is found we can solve the instance by solving a number of tractable instances. Parameterized complexity provides an adequate framework for studying and solving this algorithmic task, where the size of the backdoor set provides a natural parameter. In this survey we present some recent parameterized complexity results on CSP backdoor sets, focusing on backdoor sets into islands of tractability that are defined in terms of constraint languages.

Cite as

Serge Gaspers, Sebastian Ordyniak, and Stefan Szeider. Backdoor Sets for CSP. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 137-157, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InCollection{gaspers_et_al:DFU.Vol7.15301.137,
  author =	{Gaspers, Serge and Ordyniak, Sebastian and Szeider, Stefan},
  title =	{{Backdoor Sets for CSP}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{137--157},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.137},
  URN =		{urn:nbn:de:0030-drops-69626},
  doi =		{10.4230/DFU.Vol7.15301.137},
  annote =	{Keywords: Backdoor sets, Constraint satisfaction problems, Parameterized complexity, Polymorphisms}
}
Document
On the Complexity of Holant Problems

Authors: Heng Guo and Pinyan Lu

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


Abstract
In this article we survey recent developments on the complexity of Holant problems. We discuss three different aspects of Holant problems: the decision version, exact counting, and approximate counting.

Cite as

Heng Guo and Pinyan Lu. On the Complexity of Holant Problems. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 159-177, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InCollection{guo_et_al:DFU.Vol7.15301.159,
  author =	{Guo, Heng and Lu, Pinyan},
  title =	{{On the Complexity of Holant Problems}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{159--177},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.159},
  URN =		{urn:nbn:de:0030-drops-69630},
  doi =		{10.4230/DFU.Vol7.15301.159},
  annote =	{Keywords: Computational complexity, Counting complexity, Dichotomy theorems, Approximate counting, Holant problems}
}
Document
Parameterized Constraint Satisfaction Problems: a Survey

Authors: Gregory Gutin and Anders Yeo

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


Abstract
We consider constraint satisfaction problems parameterized above or below guaranteed values. One example is MaxSat parameterized above m/2: given a CNF formula F with m clauses, decide whether there is a truth assignment that satisfies at least m/2 + k clauses, where k is the parameter. Among other problems we deal with are MaxLin2-AA (given a system of linear equations over F_2 in which each equation has a positive integral weight, decide whether there is an assignment to the variables that satisfies equations of total weight at least W/2+k, where W is the total weight of all equations), Max-r-Lin2-AA (the same as MaxLin2-AA, but each equation has at most r variables, where r is a constant) and Max-r-Sat-AA (given a CNF formula F with m clauses in which each clause has at most r literals, decide whether there is a truth assignment satisfying at least sum_{i=1}^m (1-2^{r_i})+k clauses, where k is the parameter, r_i is the number of literals in clause i, and r is a constant). We also consider Max-r-CSP-AA, a natural generalization of both Max-r-Lin2-AA and Max-r-Sat-AA, order (or, permutation) constraint satisfaction problems parameterized above the average value and some other problems related to MaxSat. We discuss results, both polynomial kernels and parameterized algorithms, obtained for the problems mainly in the last few years as well as some open questions.

Cite as

Gregory Gutin and Anders Yeo. Parameterized Constraint Satisfaction Problems: a Survey. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 179-203, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InCollection{gutin_et_al:DFU.Vol7.15301.179,
  author =	{Gutin, Gregory and Yeo, Anders},
  title =	{{Parameterized Constraint Satisfaction Problems: a Survey}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{179--203},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.179},
  URN =		{urn:nbn:de:0030-drops-69641},
  doi =		{10.4230/DFU.Vol7.15301.179},
  annote =	{Keywords: Constraint satisfaction problems, Fixed-parameter tractability}
}
Document
Counting Constraint Satisfaction Problems

Authors: Mark Jerrum

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


Abstract
This chapter surveys counting Constraint Satisfaction Problems (counting CSPs, or #CSPs) and their computational complexity. It aims to provide an introduction to the main concepts and techniques, and present a representative selection of results and open problems. It does not cover holants, which are the subject of a separate chapter.

Cite as

Mark Jerrum. Counting Constraint Satisfaction Problems. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 205-231, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InCollection{jerrum:DFU.Vol7.15301.205,
  author =	{Jerrum, Mark},
  title =	{{Counting Constraint Satisfaction Problems}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{205--231},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.205},
  URN =		{urn:nbn:de:0030-drops-69655},
  doi =		{10.4230/DFU.Vol7.15301.205},
  annote =	{Keywords: Approximation algorithms, Computational complexity, Constraint satisfaction problems, Counting problems, Partition functions}
}
Document
The Complexity of Valued CSPs

Authors: Andrei Krokhin and Stanislav Zivny

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


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.

Cite as

Andrei Krokhin and Stanislav Zivny. The Complexity of Valued CSPs. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 233-266, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InCollection{krokhin_et_al:DFU.Vol7.15301.233,
  author =	{Krokhin, Andrei and Zivny, Stanislav},
  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 =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.233},
  URN =		{urn:nbn:de:0030-drops-69665},
  doi =		{10.4230/DFU.Vol7.15301.233},
  annote =	{Keywords: Constraint satisfaction problems, Optimisation, Tractability}
}
Document
Algebra and the Complexity of Digraph CSPs: a Survey

Authors: Benoit Larose

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


Abstract
We present a brief survey of some of the key results on the interplay between algebraic and graph-theoretic methods in the study of the complexity of digraph-based constraint satisfaction problems.

Cite as

Benoit Larose. Algebra and the Complexity of Digraph CSPs: a Survey. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 267-285, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InCollection{larose:DFU.Vol7.15301.267,
  author =	{Larose, Benoit},
  title =	{{Algebra and the Complexity of Digraph CSPs: a Survey}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{267--285},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.267},
  URN =		{urn:nbn:de:0030-drops-69677},
  doi =		{10.4230/DFU.Vol7.15301.267},
  annote =	{Keywords: Constraint satisfaction problems, Polymorphisms, Digraphs}
}
Document
Approximation Algorithms for CSPs

Authors: Konstantin Makarychev and Yury Makarychev

Published in: Dagstuhl Follow-Ups, Volume 7, The Constraint Satisfaction Problem: Complexity and Approximability (2017)


Abstract
In this survey, we offer an overview of approximation algorithms for constraint satisfaction problems (CSPs) - we describe main results and discuss various techniques used for solving CSPs.

Cite as

Konstantin Makarychev and Yury Makarychev. Approximation Algorithms for CSPs. In The Constraint Satisfaction Problem: Complexity and Approximability. Dagstuhl Follow-Ups, Volume 7, pp. 287-325, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)


Copy BibTex To Clipboard

@InCollection{makarychev_et_al:DFU.Vol7.15301.287,
  author =	{Makarychev, Konstantin and Makarychev, Yury},
  title =	{{Approximation Algorithms for CSPs}},
  booktitle =	{The Constraint Satisfaction Problem: Complexity and Approximability},
  pages =	{287--325},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-95977-003-3},
  ISSN =	{1868-8977},
  year =	{2017},
  volume =	{7},
  editor =	{Krokhin, Andrei and Zivny, Stanislav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol7.15301.287},
  URN =		{urn:nbn:de:0030-drops-69685},
  doi =		{10.4230/DFU.Vol7.15301.287},
  annote =	{Keywords: Constraint satisfaction problems, Approximation algorithms, SDP, UGC}
}
  • Refine by Author
  • 9 Krokhin, Andrei
  • 4 Zivny, Stanislav
  • 3 Bulatov, Andrei A.
  • 2 Barto, Libor
  • 2 Grohe, Martin
  • Show More...

  • Refine by Classification
  • 1 Applied computing → Economics
  • 1 Theory of computation → Approximation algorithms analysis
  • 1 Theory of computation → Constraint and logic programming
  • 1 Theory of computation → Problems, reductions and completeness

  • Refine by Keyword
  • 9 Constraint satisfaction problems
  • 4 Computational complexity
  • 3 CSP dichotomy conjecture
  • 3 Constraint satisfaction problem (CSP)
  • 3 Universal algebra
  • Show More...

  • Refine by Type
  • 23 document
  • 1 volume

  • Refine by Publication Year
  • 15 2017
  • 6 2010
  • 1 2013
  • 1 2016
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail