Mes recherches portent sur l'approximation polynomiale au pire des cas des problèmes dits difficiles d'optimisation combinatoire. Je me focalise principalement sur des approches algorithmiques simples, car au-delà des rapports d'approximation, c'est l'identification de propriétés structurelles permettant de comprendre pourquoi un problème est facile ou difficile à approcher qui motive ma recherche ; c'est une démarche que j'ai notamment entreprise sous l'angle de la recherche locale.

Par ailleurs, je cherche à approfondir la connaissance que l'on a des classes d'approximation sous l'angle du rapport différentiel, en analysant la qualité des solutions fournies par des algorithmes dédiés problèmes, mais aussi en enrichissant le cadre théorique différentiel par l'étude des réductions préservant l'approximation.

• approximation
• optima locaux

Les résultats obtenus sont de deux types : statut d'approximabilité d'un problème difficile d'optimisation combinatoire sous l'angle de la recherche locale, classification relativement à l'approximation différentielle (résultats négatifs par réduction, résultats positifs par la conception et l'analyse d'algorithmes dédiés problème).

• rapport différentiel et classification
• analyse structurelle