Wednesday, February 22, 2017

[DMANET] A new volume of surveys on CSP (open access)

"The Constraint Satisfaction Problem: Complexity and Approximability"
An edited volume of surveys (Editors A.Krokhin and S.Živný)
has just been published in the Dagstuhl Follow-Ups series.

The volume is open access and available online at

Table of Contents:
Polymorphisms, and How to Use Them. Libor Barto and Andrei Krokhin and Ross Willard
Absorption in Universal Algebra and CSP. Libor Barto and Marcin Kozik
Constraint Satisfaction Problems over Numeric Domains. Manuel Bodirsky and Marcello Mamino
Hybrid Tractable Classes of Constraint Problems. Martin C. Cooper and Stanislav Živný
Backdoor Sets for CSP. Serge Gaspers, Sebastian Ordyniak, and Stefan Szeider
On the Complexity of Holant Problems. Heng Guo and Pinyan Lu
Parameterized Constraint Satisfaction Problems: a Survey. Gregory Gutin and Anders Yeo
Counting Constraint Satisfaction Problems. Mark Jerrum
The Complexity of Valued CSPs. Andrei Krokhin and Stanislav Živný
Algebra and the Complexity of Digraph CSPs: a Survey. Benoit Larose
Approximation Algorithms for CSPs. Konstantin Makarychev and Yury Makarychev
Quantified Constraints in Twenty Seventeen. Barnaby Martin

* Contributions to be spread via DMANET are submitted to
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.