Algorithmes d'approximation

Connaissance des algorithmes classiques de graphes

Savoir produire des algorithmes polynomiaux dont la qualité du résultat est analytiquement comparable à la solution optimale, même si le problème est NP-complet. Savoir analyser cette qualité en se basant sur des propriétés structurelles du problème étudié.

En optimisation discrète, les deux principaux courants sont :
+ la résolution exacte. Pour des problèmes NP-complets cela conduit à des méthodes non polynomiales, inutilisables en pratique.
+ la résolution par heuristiques ou méta-heuristiques. Ici le problème est de savoir quelle est la qualité de la solution produite. En général aucune garantie ne peut être offerte.
Les algorithmes d’approximation sont des méthodes polynomiales qui offrent des garanties analytiquement prouvées sur la qualité du résultat produit, comparativement à la solution optimale, même si celle-ci ne peut pas être construite en temps polynomial. Ils offrent un cadre théorique et pratique pour aborder la résolution de problèmes difficiles.

Savoir produire des algorithmes polynomiaux dont la qualité du résultat est analytiquement comparable à la solution optimale, même si le problème est NP-complet. Savoir analyser cette qualité en se basant sur des propriétés structurelles du problème étudié.