Résumé de séminaire

Résumé :

The constraint satisfaction problem (CSP) is a powerful general framework in which a variety of combinatorial problems can be expressed. The aim in a constraint satisfaction problem is to find an assignment of values to the variables subject to specified constraints. This framework is used across a variety of research areas in artificial intelligence, including planning and scheduling, and in computer science, including combinatorial optimization, database theory, and complexity theory.

The optimization version of CSP is the maximum constraint satisfaction problem (Max CSP), where the goal is to find an assignment of values that maximizes the number of satisfied constraints. In general, Max CSP over any finite fixed domain (of values) is NP-hard. Hence, it is natural to look for restrictions on the problem that allow one to efficiently find an optimal assignment. Constraints are usually specified by relations, or predicates, and hence any constraint problem can be parameterized by restricting the set of allowed predicates which can be used as constraints.

The problem of determining (up to complete classification) the complexity of the CSP, the Max CSP and many other constraint problems for all possible parameter sets has attracted much attention.

For the Boolean (i.e., two-valued) case, the complexity of the standard CSP and that of Max CSP has been completely classified by Schaefer and Creignou, respectively; such problems are sometimes refered to as "generalized satisfiability problems". In this talk I will discuss recent progress in classifying the complexity of Max CSP over an arbitrary finite domain. I will describe a surprising link of the tractability in this problem with two other well established directions in combinatorial optimization: sub- and supermodular functions and Monge matrices and arrays.

This is joint work with D.Cohen, M.Cooper, P.Jeavons, and P.Jonsson

Références :

Home Page : http://web.comlab.ox.ac.uk/oucl/work/andrei.krokhin/