Abstract (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.