Homepage
Previous JFRO
Organizing committee
Contact
27th Ile-de-France Operation Research Day
Algorithmes faiblement exponentiels et FPT
Date
This day took place
Tuesday, the 20 November 2012
Place
Université Paris 6 - Laboratoire d’informatique de Paris 6 (Tour 25-26, salle 105) 4 place Jussieu 75252 Paris cedex 05
How to get there?

Program of the day


09h00-09h30
Accueil

09h30-10h45
Tutoriel sur les algorithmes faiblement exponentiels
Vangelis Paschos (LAMSADE, Université Paris-Dauphine)
Abstract : 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-12h00
Tutoriel sur la complexité paramétrée
Stéphan Thomassé (LIP, ENS Lyon)

12h00-14h00
Déjeuner

14h00-14h40
Approximation non polynomiale
Bruno Escoffier (LAMSADE, Université Paris-Dauphine)
Abstract : 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)
Abstract : 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)
Abstract : 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.6488^n).

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)
Abstract : 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.

Choose language : Français English