Dimitri Watel
COMPLEXITÉ : ALGORITHMES APPROCHÉS
Ce cours est une introduction à l'approximabilité polynomiale des problèmes d'optimisation. On recherche dans ce cours des algorithmes polynomiaux qui vont résoudre des problèmes d'optimisation sans nécessairement renvoyer une solution optimale. On cherche alors à déterminer à quelle distance de l'optimale se trouve la solution renvoyée par l'algorithme, on recherche des algorithmes pour lesquels cette distance, connue sous le nom de rapport d'approximation, n'est jamais trop élevée. Cette technique sert notamment dans le cas des problèmes pour lesquels on ne connait pas d'algorithme polynomial exact. Ce cours introduit les différentes mesures d'approximabilité, les réductions préservant les rapports d'approximation, les schémas d'approximation et les différentes techniques pour construire de tels algorithmes.
Cours
Support de cours
Slides
- Exemples d'approximations polynomiales
- Problèmes d’optimisation et algorithmes à garantie de performances
- Approximation polynomiale et programmation linéaire
- Inapproximabilité
Copyright © 2016, Dimitri Watel