Algorithmique pour l’approximation

Objectifs : L’objectif de ce cours est de présenter les méthodes générales classiques permettant d’établir des algorithmes d'approximation ainsi que des résultats de non-approximation pour des problèmes d'optimisation.

Contenu :

• Présenter le lien entre un problème de décision et d'optimisation

• Présenter les classes de problèmes d'optimisation sémantiques (en fonction du rapport d'approximation) et syntaxiques (en fonction de la formulation logique) et la liaison entre les deux types de classes

• Résultats d’approximation pour des problèmes d'optimisation classiques (Voyageur de commerce, Stable, Couverture de sommets et d’ensembles, Coloration, Satisfiabilité, Sac à dos)

• Notions de réduction préservant le rapport d'approximation et son utilisation pour l'obtention de résultats d'approximation et non-approximation

• Présenter de nouveaux paradigmes d’approximation, notamment l’approximation modérément exponentielle et l’approximation paramétrée

Bibliographie

• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag, 1999.

• D. Hochbaum, Approximation Algorithms for NP-Hard Problems, Course Technology, 1996.

• V. Th. Paschos, Complexité et Approximation Polynomiale, Hermès, 2004.

• V. Vazirani, Approximation Algorithms, Springer-Verlag, 2001.