Abstract FR:

L'objet de cette thèse est l'étude de transformations entre problèmes d'optimisation combinatoires dont la version décision est NP-complète. Ces réductions doivent être adaptées au point de vue approximation c'est-à-dire non seulement faire correspondre les solutions optimales de deux problèmes mais surtout conserver diffèrent type d'information concernant les solutions qui sont simplement réalisables. Nous proposons tout d'abord un état de l'art sur les réductions préservant l'approximation en montrant comment l'évolution de cet outil permet de s'inscrire dans le cadre optimisation et surtout approximation. Nous présentons ensuite des résultats d'équivalence que nous établissons par la mise en œuvre de réductions continues. Ces résultats sont regroupés en hiérarchies à l'intérieur desquelles nous proposons des réductions continues entre les problèmes. Nous établissons également des réductions entres différentes hiérarchies. Des couches d'équi-approximabilité sont ainsi construites à l'intérieur de la classe des problèmes d'optimisation NP