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
Abstract : The theory of NP-completeness tells us that for many optimization problems, there is no hope for finding an efficient algorithm computing an optimal solution. Based on this, two classical approaches have been developped to deal with these problems. The first one, called polynomial- time approximation, consists in designing efficient algorithms computing a solution that is close to an optimal one. The second one, called param- eterized complexity, consists in designing exact algorithms which com- binatorial explosion is captured by a carefully chosen parameter of the instance. The goal of this thesis is twofold. First, we study and apply classical methods from these two domains in order to obtain positive and negative results for two optimization problems in graphs: a partitioning problem called Sparsest k-Compaction, and a cardinality constraint subgraph problem called Sparsest k-Subgraph. Then, we present how the different methods from these two domains have been combined in recent years in a concept called parameterized approximation. In particular, we study the links between approximation and kernelization algorithms.
Document type :
Theses
Complete list of metadatas

https://tel.archives-ouvertes.fr/tel-01488596
Contributor : Abes Star <>
Submitted on : Monday, March 13, 2017 - 5:58:06 PM
Last modification on : Wednesday, January 23, 2019 - 1:52:02 PM
Long-term archiving on : Wednesday, June 14, 2017 - 3:15:22 PM

File

41464_WATRIGANT_2014_archivage...
Version validated by the jury (STAR)

Identifiers

  • 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⟩

Share

Metrics

Record views

273

Files downloads

766