Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

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

  1. Max CSP is tractable whenever the constraint language is supermodular with respect to a lattice; and
  2. 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.

Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30