## Séminaire Algorithmique |

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.