Skip to main content

Research Repository

Advanced Search

All Outputs (69)

The complexity of soft constraint satisfaction (2006)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2006). The complexity of soft constraint satisfaction. Artificial Intelligence, 170(11), 983-1016. https://doi.org/10.1016/j.artint.2006.04.002

Over the past few years there has been considerable progress in methods to systematically analyse the complexity of constraint satisfaction problems with specified constraint types. One very powerful theoretical development in this area links the com... Read More about The complexity of soft constraint satisfaction.

Maximum constraint satisfaction on diamonds (2005)
Presentation / Conference Contribution
Krokhin, A., & Larose, B. (2005, December). Maximum constraint satisfaction on diamonds. Presented at 11th International Conference on Principles and Practice of Constraint Programming {(CP'05)

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.

Identifying efficiently solvable cases of Max CSP (2004)
Presentation / Conference Contribution
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2004, December). Identifying efficiently solvable cases of Max CSP. Presented at 21st International Symposium on Theoretical Aspects of Computer Science

Recognizing frozen variables in constraint satisfaction problems (2004)
Journal Article
Jonsson, P., & Krokhin, A. (2004). Recognizing frozen variables in constraint satisfaction problems. Theoretical Computer Science, 329(1-3), 93-113. https://doi.org/10.1016/j.tcs.2004.08.006

In constraint satisfaction problems over finite domains, some variables can be frozen, that is, they take the same value in all possible solutions. We study the complexity of the problem of recognizing frozen variables with restricted sets of constra... Read More about Recognizing frozen variables in constraint satisfaction problems.

Complexity classification in qualitative temporal constraint reasoning (2004)
Journal Article
Jonsson, P., & Krokhin, A. (2004). Complexity classification in qualitative temporal constraint reasoning. Artificial Intelligence, 160(1-2), 35-51. https://doi.org/10.1016/j.artint.2004.05.010

We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allen's interval algebra. We identify all tractable fragments and show that ever... Read More about Complexity classification in qualitative temporal constraint reasoning.

A maximal tractable class of soft constraints (2004)
Journal Article
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2004). A maximal tractable class of soft constraints. Journal of Artificial Intelligence Research, 22, 1-22. https://doi.org/10.1613/jair.1400

Many researchers in artificial intelligence are beginning to explore the use of soft constraints to express a set of (possibly conflicting) problem requirements. A soft constraint is a function defined on a collection of variables which associates so... Read More about A maximal tractable class of soft constraints.

Constraint satisfaction problems on intervals and lengths (2004)
Journal Article
Krokhin, A., Jeavons, P., & Jonsson, P. (2004). Constraint satisfaction problems on intervals and lengths. SIAM Journal on Discrete Mathematics, 17(3), 453-477. https://doi.org/10.1137/s0895480102410201

We study interval-valued constraint satisfaction problems (CSPs), in which the aim is to find an assignment of intervals to a given set of variables subject to constraints on the relative positions of intervals. Many well-known problems such as INTER... Read More about Constraint satisfaction problems on intervals and lengths.

First-Order Definable Retraction Problems for Posets and Reflexive Graphs (2004)
Presentation / Conference Contribution
Dalmau, V., Krokhin, A., & Larose, B. (2023, July). First-Order Definable Retraction Problems for Posets and Reflexive Graphs. Presented at 19th Annual IEEE Symposium on Logic in Computer Science (LICS'04), Turku, Finland

A retraction from a structure P to its substructure Q is a homomorphism from P onto Q that is the identity on Q. We present an algebraic condition which completely characterises all posets and all reflexive graphs Q with the following property: the c... Read More about First-Order Definable Retraction Problems for Posets and Reflexive Graphs.

Quantified constraints: Algorithms and complexity (2003)
Presentation / Conference Contribution
Boerner, F., Bulatov, A., Jeavons, P., & Krokhin, A. (2003, December). Quantified constraints: Algorithms and complexity. Presented at 17th International Workshop on Computer Science Logic

A tractable class of soft constraints. (2003)
Presentation / Conference Contribution
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2003, December). A tractable class of soft constraints. Presented at 18th International Joint Conference on Artificial Intelligence {(IJCAI'03)

Soft constraints: complexity and multimorphisms (2003)
Presentation / Conference Contribution
Cohen, D., Cooper, M., Jeavons, P., & Krokhin, A. (2003, December). Soft constraints: complexity and multimorphisms. Presented at Proceedings of 9th International Conference on Principle and Practice of Constraint Programming {(CP'03)

Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra (2003)
Journal Article
Krokhin, A., Jeavons, P., & Jonsson, P. (2003). Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra. Journal of the ACM, 50(5), 591-640. https://doi.org/10.1145/876638.876639

Allen's interval algebra is one of the best established formalisms for temporal reasoning. This article provides the final step in the classification of complexity for satisfiability problems over constraints expressed in this algebra. When the const... Read More about Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra.

Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey (2003)
Presentation / Conference Contribution
Krokhin, A., Bulatov, A., & Jeavons, P. (2003, May). Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey. Presented at 33rd International Symposium on Multiple-Valued Logic (ISMVL'03)

Many computational problems arising in artificial intelligence, computer science and elsewhere can be represented as constraint satisfaction and optimization problems. In this short survey we discuss an approach that is related to the algebraic compo... Read More about Functions of multiple-valued logic and the complexity of constraint satisfaction: A short survey.

Solving order constraints in logarithmic space (2003)
Presentation / Conference Contribution
Krokhin, A., & Larose, B. (2003, January). Solving order constraints in logarithmic space. Presented at Proceedings of the 20th International Symposium on Theoretical Aspects of Computer Science {(STACS'03) Berlin, Berlin

We combine methods of order theory, finite model theory, and universal algebra to study, within the constraint satisfaction framework, the complexity of some well-known combinatorial problems connected with a finite poset. We identify some conditions... Read More about Solving order constraints in logarithmic space.