Contributions à l'approximation et à la paramétrisation en optimisation combinatoire
02/12/2022 à 14h00
M. Nikolaos MELISSINOS présente ses travaux en soutenance le 02/12/2022 à 14h00
À l'adresse suivante : Université Paris Dauphine - PSL, Pl. du Maréchal de Lattre de Tassigny 75775 PARIS Cedex 16 - Salle des thèses D520
En vue de l'obtention du diplôme : Doctorat en Informatique
La soutenance est publique
Titre des travaux
Contributions à l'approximation et à la paramétrisation en optimisation combinatoire
École doctorale
École doctorale Dauphine SDOSE
Équipe de recherche
UMR 7243 - Laboratoire d’Analyse et de Modélisation de Systèmes d’Aide à la Décision
Section CNU
27 - Informatique
Directeur(s)
M. Laurent GOURVES
Membres du jury
| Nom | Qualité | Établissement | Rôle |
|---|---|---|---|
| M. Laurent GOURVES | Directeur de recherche | UNIVERSITE PARIS DAUPHINE - PSL | Directeur de thèse |
| M. Bruno ESCOFFIER | Professeur des universités | SORBONNE UNIVERSITE | Rapporteur |
| M. Bernard RIES | Professeur | Université de Fribourg | Rapporteur |
| Mme Cristina BAZGAN | Professeur des universités | UNIVERSITE PARIS DAUPHINE - PSL | Examinatrice |
| Mme Marthe BONAMY | Chargé de recherche CNRS | UNIVERSITE DE BORDEAUX | Examinatrice |
| M. Ararat HARUTYUNYAN | Maître de conférences | UNIVERSITE PARIS DAUPHINE - PSL | Examinateur |
| M. Aris PAGOURTZIS | Professeur | National Technical University of Athens | Examinateur |
Résumé
En informatique, un problème d’optimisation est un problème où l’on essaie de trouver la meilleure solution parmi toutes les solutions réalisables. Ce type de problème peut provenir d’autres sciences, comme les mathématiques, la physique, l’économie, ou même de l’industrie. Lorsque nous traitons un tel problème, notre objectif est de proposer des algorithmes efficaces qui calculent des solutions optimales pour toute instance donnée. Malheureusement, dans de nombreux cas, nous devons traiter des problèmes NP-difficiles pour lesquels il est communément admis qu’aucun algorithme de la sorte n’existe. Pour cette raison, plusieurs approches et techniques ont été développées pour traiter la NP- difficulté . Dans ce manuscrit, nous nous intéressons à deux approches spécifiques. Premièrement, nous considérons les solutions approchées. Le concept d’approximation en temps polynomial existe depuis des décennies. Ici, au lieu d’essayer de trouver la ”meilleure” solution, nous cherchons une ”bonne” solution qui peut être calculée en temps polynomial. En particulier, nous voulons développer un algorithme d’approximation en temps polynomial qui retourne des solutions aussi proches de l’optimum que possible. Dans la deuxième approche, nous considérons des instances restreintes du problème. Dans une telle approche, nous faisons des hypothèses supplémentaires sur l’instance du problème donné. Cette idée vient du fait que parfois nous ne sommes pas intéressés à résoudre toutes les instances d’un problème mais seulement une sous-classe et les instances de cette sousclasse ont des propriétés que nous pouvons exploiter dans nos algorithmes. Dans cette thèse, nous appliquons principalement cette approche aux problèmes de graphes. Certaines hypothèses sont liées à la structure de l’entrée donnée (pour les problèmes de graphes, cela peut signifier par exemple que le graphe est régulier ou biparti) tandis que d’autres hypothèses concernent la taille d’un paramètre spécifique (comme le degré ou la largeur d’arbre du graphe donné). Dans le second cas, nous disons que nous sommes intéressés par la complexité paramétrée du problème. Lorsque nous considérons un paramètre, notre objectif est de trouver des algorithmes exacts dont le temps d’exécution est de la forme f (k)nO(1), où k est la taille du paramètre et n la taille de l’instance. Lorsque cette approche est possible, nous disons que nous avons un algorithme fpt. Dans le premier chapitre, nous étudions des problèmes similaires au problème bien connu de la somme de sous-ensembles (Subset Sum). En particulier, nous étudions le problème Ratio des sommes de sous-ensembles (SSR) et certaines de ses variantes. Dans SSR, nous avons en entrée un ensemble A d’entiers positifs et nous voulons trouver deux sous-ensembles disjoints qui ont un rapport aussi proche de un que possible. Nous présentons un nouvel algorithme FPTAS pour SSR et nous développons un cadre générique qui donne des FPTAS pour une famille de variantes du SSR sous certaines conditions. Dans la suite de ce manuscrit, nous étudions les problèmes de graphes. Certains de ces problèmes sont des variantes de problèmes de graphes bien connus comme le problème Feedback Vertex Set et le problème Vertex Coloring. Pour ces problèmes, nous présentons des algorithmes d’approximation, des résultats d’inapproximabilité et des algorithmes paramétrés. Enfin, en utilisant des hypothèses standard comme l’hypothèse du temps exponentiel (ETH), nous présentons des bornes inférieures sur le temps d’exécution de nos algorithmes paramétrés qui correspondent au temps d’exécution de nos algorithmes.