Events

7 July 2010

Bât. 1. 1er étage
Microsoft Research - Inria Joint Centre
Parc Orsay Université

Optimisation de contraintes par algorithmes gloutons
Claire Mathieu
Brown University.

Comment expliquer les bonnes performances d’algorithmes de type glouton pour divers problèmes d’optimisation?

Nous étudions d’abord le problème de la coupe maximale, où le but est de partitionner les sommets d’un graphe en deux parties en maximisant le nombre d’aretes traversant la coupe. Une variante de l’algorithme glouton produit une coupe quasi-optimale. L’algorithme, après une phase d’initialisation brève mais délicate, peut ensuite ajouter les sommets de part de d’autre de la coupe de manière gloutonne, S’ils sont ajoutés dans un ordre aléatoire, le résultat sera quasi-optimal: sa valeur ne diffère de l’optimum que par une constante arbitrairement petite fois |V|^2. L’analyse utilise un argument de martingale. Puis nous présenterons une généralisation a des problèmes de satisfaction de contraintes (k-CSP) et a des problèmes de classement.

Ce travail est une collaboration avec Warren Schudy.