Skip to main content

Research Repository

Advanced Search

All Outputs (6)

Binarisation for Valued Constraint Satisfaction Problems (2017)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., Krokhin, A., Powell, R., & Zivny, S. (2017). Binarisation for Valued Constraint Satisfaction Problems. SIAM Journal on Discrete Mathematics, 31(4), 2279-2300. https://doi.org/10.1137/16m1088107

We study methods for transforming valued constraint satisfaction problems (VCSPs) to binary VCSPs. First, we show that the standard dual encoding preserves many aspects of the algebraic properties that capture the computational complexity of VCSPs. S... Read More about Binarisation for Valued Constraint Satisfaction Problems.

The complexity of general-valued CSPs (2017)
Journal Article
Kolmogorov, V., Krokhin, A., & Rolínek, M. (2017). The complexity of general-valued CSPs. SIAM Journal on Computing, 46(3), 1087-1110. https://doi.org/10.1137/16m1091836

An instance of the valued constraint satisfaction problem (VCSP) is given by a finite set of variables, a finite domain of labels, and a sum of functions, each function depending on a subset of the variables. Each function can take finite values spec... Read More about The complexity of general-valued CSPs.

Robust algorithms with polynomial loss for near-unanimity CSPs (2017)
Presentation / Conference Contribution
Dalmau, V., Kozik, M., Krokhin, A., Makarychev, K., Makarychev, Y., & Oprsal, J. (2017). Robust algorithms with polynomial loss for near-unanimity CSPs. In P. N. Klein (Ed.), Proceedings of the twenty-eighth Annual ACM-SIAM symposium on discrete algorithms (340-357). https://doi.org/10.1137/1.9781611974782.22

An instance of the Constraint Satisfaction Problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimiz... Read More about Robust algorithms with polynomial loss for near-unanimity CSPs.

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.