Approximation et complexité paramétrée de problèmes d’optimisation dans les graphes : partitions et sous-graphes

Rémi Watrigant 1
1 MAORE - Méthodes Algorithmes pour l'Ordonnancement et les Réseaux
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : La théorie de la NP-complétude nous apprend que pour un certain nombre de problèmes d'optimisation, il est vain d'espérer un algorithme efficace calculant une solution optimale. Partant de ce constat, un moyen pour contourner cet obstacle est de réaliser un compromis sur chacun de ces critères, engendrant deux approches devenues classiques. La première, appelée approximation polynomiale, consiste à développer des algorithmes efficaces et retournant une solution proche d'une solution optimale. La seconde, appelée complexité paramétrée, consiste à développer des algorithmes retournant une solution optimale mais dont l'explosion combinatoire est capturée par un paramètre de l'entrée bien choisi. Cette thèse comporte deux objectifs. Dans un premier temps, nous proposons d'étudier et d'appliquer les méthodes classiques de ces deux domaines afin d'obtenir des résultats positifs et négatifs pour deux problèmes d'optimisation dans les graphes : un problème de partition appelé Sparsest k-Compaction, et un problème de recherche d'un sous-graphe avec une cardinalité fixée appelé Sparsest k-Subgraph. Dans un second temps, nous présentons comment les méthodes de ces deux domaines ont pu se combiner ces dernières années pour donner naissance au principe d'approximation paramétrée. En particulier, nous étudierons les liens entre approximation et algorithmes de noyaux.
Type de document :
Thèse
Géométrie algorithmique [cs.CG]. Université Montpellier II - Sciences et Techniques du Languedoc, 2014. Français. 〈NNT : 2014MON20100〉
Liste complète des métadonnées

https://tel.archives-ouvertes.fr/tel-01488596
Contributeur : Abes Star <>
Soumis le : lundi 13 mars 2017 - 17:58:06
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : mercredi 14 juin 2017 - 15:15:22

Fichier

41464_WATRIGANT_2014_archivage...
Version validée par le jury (STAR)

Identifiants

  • HAL Id : tel-01488596, version 1

Collections

Citation

Rémi Watrigant. Approximation et complexité paramétrée de problèmes d’optimisation dans les graphes : partitions et sous-graphes. Géométrie algorithmique [cs.CG]. Université Montpellier II - Sciences et Techniques du Languedoc, 2014. Français. 〈NNT : 2014MON20100〉. 〈tel-01488596〉

Partager

Métriques

Consultations de la notice

212

Téléchargements de fichiers

469