Algorithmique pour l’approximation

Ects : 3

Enseignant responsable :

  • CRISTINA BAZGAN
  • EVANGELOS PASCHOS

Volume horaire : 15

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.