Approximation polynomiale de problèmes d’optimisation : aspects structurels et opérationnels
Institution:
Paris 9Disciplines:
Directors:
Abstract EN:
This thesis deals with the study of NPO-problems (optimization problems the decision version of which is in NP), and more precisely the theory of worst case polynomial approximation. In this problematic, we aim at determining how it is possible to produce efficiently a feasible solution achieving a certain quality, quality measured either by the standard ratio or by the differential ratio. Our work can be divided into two parts : - The structure of approximation classes, structure which emerges from the introduction of approximation preserving reductions which induce notions of completeness. - Polynomial approximation of some NPO problems: we studied approximation properties of the weighted coloring problem, the probabilistic coloring problem and the quadratic set covering problem using the standard ratio, and satisfiability problems using the differential ratio.
Abstract FR:
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.