Contributions to approximation and parameterization in combinatorial optimization
Contributions à l'approximation et à la paramétrisation en optimisation combinatoire.
Melissinos, Nikolaos (2022), Contributions to approximation and parameterization in combinatorial optimization, doctoral thesis prepared under the supervision of Gourvès, Laurent, Université Paris sciences et lettres
Author(s)
Melissinos, NikolaosUnder the direction of
Gourvès, LaurentAbstract (FR)
L'étude des problèmes combinatoires est une tâche importante car ils sont l'abstraction de très nombreux problèmes auxquels nous sommes confrontés dans notre vie depuis très longtemps. Dans cette thèse, nous étudions des variantes de problèmes d'optimisation combinatoire classiques tels que : SubsetSum, Feedback Vertex Set et Coloring. Pour ces problèmes, nous présentons d'abord des résultats de NP-difficulté pour de nombreux cas particuliers. Ensuite, nous considérons des solutions d'approximation; nous donnons quelques algorithmes d'approximation et des bornes inférieures sur le rapport d'approximation sous des hypothèses standards. Enfin, nous présentons quelques algorithmes paramétrés qui construisent des solutions exactes et nous prouvons leur optimalité sous l'hypothèse ETH.Abstract (EN)
The study of combinatorial problems is an important task as they are abstraction of many problems that we face in our life for a very long time. In this thesis we study variants of classical combinatorial optimization problems such as, Subset Sum, Feedback VertexSet and Coloring. For these problems we first present NP-hardness results for many special cases. Then, we consider approximation solutions; we give some approximation algorithms and lower bounds on approximation ratio under standard assumptions. thesis Finally, we present some parameterized algorithms that compute exact solutions and we prove their optimality under the Exponential Time Hypothesis.Subjects / Keywords
Optimisation combinatoire; Complexité standard; Approximation; Complexité paramétrée; Problèmes de graphes; Combinatorial optimization; Computational complexity; Approximation; Parameterized complexity; Graph problemsRelated items
Showing items related by title and author.
-
Cornu, Marek (2017-12-18) Thèse
-
Boria, Nicolas (2011) Thèse
-
Ould Mohamed Lemine, Mohamed (2014-06) Thèse
-
Résolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnée Belhoul, Lyes (2014-12) Thèse