Professor Andrei Krokhin's Outputs (3)

Supermodular functions and the complexity of MAX CSP (2005)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2005). Supermodular functions and the complexity of MAX CSP. Discrete Applied Mathematics, 149(1-3), 53-72. https://doi.org/10.1016/j.dam.2005.03.003

In this paper we study the complexity of the maximum constraint satisfaction problem (MAX CSP) over an arbitrary finite domain. An instance of MAX CSP consists of a set of variables and a collection of constraints which are applied to certain specifi... Read More about Supermodular functions and the complexity of MAX CSP.

Classifying the complexity of constraints using finite algebras (2005)
Journal Article
Bulatov, A., Jeavons, P., & Krokhin, A. (2005). Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34(3), 720-742. https://doi.org/10.1137/s0097539700376676

Many natural combinatorial problems can be expressed as constraint satisfaction problems. This class of problems is known to be NP-complete in general, but certain restrictions on the form of the constraints can ensure tractability. Here we show that... Read More about Classifying the complexity of constraints using finite algebras.

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.