Journées Franciliennes de Recherche Opérationnelle
ROADEF




Retour

journee.html

Programme de la 27-ème journée JFRO

LE MARDI 20 NOVEMBRE 2012

Sur le thème

Algorithmes faiblement exponentiels et FPT

A L’Université Paris 6
Laboratoire d’informatique de Paris 6 (Tour 25-26, salle 105)
4 place Jussieu 75252 Paris cedex 05

Plan d’accès Jussieu

Inscription : merci de remplir le formulaire d’inscription

9h00-9h30 Accueil des participants
9h30-10h45

Tutoriel sur les algorithmes faiblement exponentiels

Vangelis Paschos

LAMSADE, Université Paris-Dauphine


slides

Il est bien connu que les problèmes NP-difficiles peuvent être résolus optimalement par des algorithmes qui opèrent en temps exponentiel (ou pire). Des méthodes classiques, comme l’énumération exhaustive, les diverses versions de "branch-and-bound", la programmation dynamique, etc., sont très largement utilisées pour résoudre ces problèmes. Concernant la complexité au pire de cas de ces méthodes, à part éventuellement pour la programmation dynamique, nous avons seulement des évaluations assez triviales et directes. La conception des algorithmes faiblement exponentiels (programme de recherche systématiquement étudié seulement à partir des débuts des années 2000) tente de fournir des nouvelles méthodes de développement des algorithmes exacts ainsi que des outils mathématiques pour l’analyse de leur complexité au pire des cas. Cet exposé présentera les plus importants parmi ces méthodes et outils ainsi que des exemples de leur utilisation.

10h45-12h

Tutoriel sur la complexité paramétrée

Stéphan Thomassé

LIP, ENS Lyon


12h00-14h00 Pause déjeuner
14h-14h40

Approximation non polynomiale

Bruno Escoffier

LAMSADE, Université Paris-Dauphine


slides

Lorsque l’on considère un problème NP-difficile, différentes techniques permettent de concevoir des algorithmes de complexité certes exponentielle mais bien plus faible que celle obtenue par recherche exhaustive par exemple. Si le problème considéré est de plus NP-difficile à approcher, on peut alors se demander s’il est possible d’obtenir un algorithme approché certes non polynomial mais significativement plus rapide que les algorithmes exacts. Il s’agit autrement dit d’étudier la possibilité d’obtenir un compromis entre temps de calcul et qualité de la solution. Dans cet exposé, je présenterai quelques résultats et techniques relatifs à cette problématique des algorithmes approchés faiblement exponentiels, ainsi qu’à celle, voisine, des algorithmes approchés FPT.

14h40-15h20

Un noyau polynomial pour le problème de la complétion en graphes d’intervalles propres

Anthony Pérez

LIFO, Université d’Orléans


Dans cet exposé, je présenterai un algorithme de noyau polynomial pour le problème Proper Interval Completion, où l’instance consiste en un graphe G = (V,E) et un entier k et où l’objectif est de décider s’il existe un ensemble F inclus dans (VxV)\E et de taille au plus k tel que le graphe H = (V, E∪F) est un graphe d’intervalle propre. Pour conclure, je mettrai en parallèle ce résultat avec d’autres résultats connus pour des problèmes de complétion de graphes, et terminerai sur une conjecture pour caractériser les problèmes de complétion admettant un noyau polynomial.

15h20-15h40 Pause
15h40-16h20

Un algorithme exponentiel pour l’étiquetage L(2,1) de graphes

Mathieu Liedloff

LIFO, Université d’Orléans


slides

Un étiquetage L(2,1) d’un graphe est une fonction qui, à chaque sommet, associe un entier positif tel que :

  • les étiquettes de sommets adjacents diffèrent d’au moins 2 ;
  • pour tout couple de sommets ayant un voisin commun, leurs étiquettes sont différentes.
La largeur d’un tel étiquetage L(2,1) est le plus grand entier utilisé pour étiqueter les sommets. Etant donné un graphe, le problème d’optimisation demande de calculer un étiquetage L(2,1) de plus petite largeur possible. Dans cet exposé nous présenterons un algorithme exponentiel pour résoudre ce problème NP-difficile en temps O(2.6488n).
16h20-17h00

Problèmes de domination sur les graphes, paramétrés par la largeur arborescente

Mathieu Chapelle

IGM, Université Paris-Est Marne-La-Vallée


slides

De nombreux problèmes de graphes, difficiles (en complexité classique ou paramétrée) dans le cas général, peuvent être résolus efficacement lorsqu’ils sont restreints à des graphes de petite largeur arborescente. Du point de vue de la complexité paramétrée, très peu de problèmes de graphes sont connus pour ne pas admettre d’algorithme FPT lorsqu’ils sont paramétrés par la largeur arborescente du graphe donné en entrée, sous l’hypothèse que FPT≠W[1]. Dans cet exposé, je présenterai une nouvelle collection de problèmes n’admettant pas d’algorithme FPT lorsque paramétrés par la largeur arborescente.