Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.
Résumé du séminaire du Mardi 5 Juin 2012
On the Maximum Constraint Satisfaction Problem
par Johan Thapper (LIX)
An instance of the maximum constraint satisfaction problem (Max CSP) is specified by a set of variables, a domain, and a set of constraints. Each constraint imposes a relation over the domain on a subset of variables. The relations are chosen from a fixed set called the constraint language. The goal is to find an assignment of domain values to the variables that satisfies as many constraints as possible. The question is: Given a fixed constraint language, what is the computational complexity of Max CSP?
Until not long ago, all evidence pointed to, and it was conjectured that
- Max CSP is tractable whenever the constraint language is supermodular with respect to a lattice; and
- This is essentially the only source of tractability for Max CSP.
I will present recent results showing that (1) is correct and that (2) is false.
The talk is based on joint work with Peter Jonsson, Fredrik Kuivinen, and Stanislav Zivny.