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 cer- tain nombre de problèmes d’optimisation, il est vain d’espérer un algo- rithme 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 solu- tion 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.
Mots-clés : complexité
Type de document :
Thèse
Recherche opérationnelle [cs.RO]. Université Montpellier II Sciences et techniques, 2014. Français
Liste complète des métadonnées

Littérature citée [121 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/tel-01378603
Contributeur : Rodolphe Giroudeau <>
Soumis le : lundi 10 octobre 2016 - 14:48:21
Dernière modification le : jeudi 11 janvier 2018 - 02:03:54
Document(s) archivé(s) le : samedi 4 février 2017 - 01:25:38

Fichier

Identifiants

  • HAL Id : tel-01378603, 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. Recherche opérationnelle [cs.RO]. Université Montpellier II Sciences et techniques, 2014. Français. 〈tel-01378603〉

Partager

Métriques

Consultations de la notice

89

Téléchargements de fichiers

119