Descriptif
Définition d'un problème NP-difficile. Définition d'un algorithme approché. Les différentes mesures d'approximabilité. Les réductions préservant les rapports d'approximation. Les schémas d'approximation. L'obtention de solution approchées par techniques locales, d'arrondis,...L'algorithmique 'on-line'.Objectifs pédagogiques
Etre capable de classifier les problèmes NP-difficiles en fonction de la difficulté de leur approximabilité.
30 heures en présentiel
