Le 31/10/2005 par escoffier :

Thèse présentée en vue de l'obtention du titre de docteur en Informatique de l'Université Paris Dauphine

par Bruno ESCOFFIER

le vendredi 04 novembre 2005, à 14h, en salle des thèses, à l'Université Paris Dauphine
Place du Maréchal de Lattre de Tassigny - Paris 16°


Titre : Approximation polynomiale de problèmes d'optimisation : aspects structurels et opérationnels

Directeur de these : Vangelis Paschos

Jury :

Giorgio AUSIELLO, professeur à l'Université La Sapienza, Rome, Italie
Dominique DE WERRA, professeur à l'EPFL, Lausanne, Suisse
Peter L. HAMMER, professeur à l'Université Rutgers, NJ, USA
Jean-Claude KONIG, professeur à l'Université Montpellier II
Vangelis Th. PASCHOS, professeur à l'Université Paris Dauphine
Christophe PICOULEAU, professeur au CNAM


Résumé :
Cette thèse s'inscrit dans le domaine de l'étude des problèmes de
NPO (problèmes d'optimisation dont la version décision est dans NP), et plus particulièrement dans la théorie de l'approximation polynomiale de ces problèmes. Il s'agit d'étudier la possibilité de fournir efficacement des solutions réalisables ayant une certaine qualité, qualité que nous mesurons tantôt par le rapport standard, tantôt par le rapport différentiel. Deux aspects principaux se dégagent dans notre travail :
- La structure des classes d'approximation : il s'agit de structurer les classes classiques par l'introduction de réductions qui préservent certains types d'approximation et qui induisent des notions de complétude.
- L'approximation polynomiale de problèmes de NPO : nous avons étudié les problèmes de la coloration pondérée, de la coloration probabiliste et de la couverture d'ensemble quadratique selon le rapport standard, ainsi que des problèmes de satisfiabilité selon le rapport différentiel.