All Outputs (5)

Polymorphisms, and how to use them (2017)
Book Chapter
Barto, L., Krokhin, A., & Willard, R. (2017). Polymorphisms, and how to use them. In A. Krokhin, & S. Živný (Eds.), The constraint satisfaction problem : complexity and approximability (1-44). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/dfu.vol7.15301.1

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.

The complexity of Valued CSPs (2017)
Book Chapter
Krokhin, A., & Živný, S. (2017). The complexity of Valued CSPs. In A. Krokhin, & S. Živný (Eds.), The constraint satisfaction problem : complexity and approximability (233-266). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/dfu.vol7.15301.9

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 gen... Read More about The complexity of Valued CSPs.

Towards a Characterization of Constant-Factor Approximable Min CSPs (2014)
Book Chapter
Dalmau, V., Krokhin, A., & Manokaran, R. (2015). Towards a Characterization of Constant-Factor Approximable Min CSPs. In P. Indyk (Ed.), Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms : San Diego, California, USA, January 4-6, 2015 (847-857). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611973730.58

We study the approximability of Minimum Constraint Satisfaction Problems (Min CSPs) with a fixed finite constraint language Γ on an arbitrary finite domain. The goal in such a problem is to minimize the number of unsatisfied constraints in a given in... Read More about Towards a Characterization of Constant-Factor Approximable Min CSPs.

Dualities for constraint satisfaction problems (2008)
Book Chapter
Bulatov, A., Krokhin, A., & Larose, B. (2008). Dualities for constraint satisfaction problems. In N. Creignou, P. Kolaitis, & H. Vollmer (Eds.), Complexity of constraints : an overview of current research themes (93-124). Springer Verlag. https://doi.org/10.1007/978-3-540-92800-3_5

In a nutshell, a duality for a constraint satisfaction problem equates the existence of one homomorphism to the non-existence of other homomorphisms. In this survey paper, we give an overview of logical, combinatorial, and algebraic aspects of the fo... Read More about Dualities for constraint satisfaction problems.

The complexity of constraint satisfaction: an algebraic approach (2005)
Book Chapter
Krokhin, A., Bulatov, A., & Jeavons, P. (2005). The complexity of constraint satisfaction: an algebraic approach. In V. B. Kudryavtsev, & I. G. Rosenberg (Eds.), Structural theory of automata, semigroups, and universal algebra (181-213). Springer Netherlands. https://doi.org/10.1007/1-4020-3817-8_8

Many computational problems arising in artificial intelligence, computer science and elsewhere can be represented as constraint satisfaction and optimization problems. In this survey paper we discuss an algebraic approach that has proved to be very s... Read More about The complexity of constraint satisfaction: an algebraic approach.