ECTS : 3
Description du contenu de l'enseignement :
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.
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, lectures recommandées :
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.