De nombreux problèmes d'optimisation sont NP-complets. Nous ne connaissons pas de problème NP-complet qui admette un algorithme optimal de résolution s'exécutant en temps polynomial en la taille de l'instance (sinon P=NP serait établi), et l'intuition commune est que P =/= NP. Pour ces problèmes, la recherche de solutions optimales peut donc être prohibitive. Les algorithmes d'approximation offrent un compromis intéressant: par définition, ils s'exécutent en temps polynomial et fournissent des solutions dont la qualité est garantie. Nous introduirons la notion d'algorithme d'approximation et de schéma d'approximation en temps polynomial, et nous illustrerons ces notions sur de nombreux exemples. Nous montrerons également comment établir qu'un problème n'admet pas d'algorithme d'approximation (à moins que P=NP), ou comment établir une borne inférieure au facteur d'approximation de tout algorithme d'approximation (sauf si P=NP).
By Dominique Barbolosi
By Dominique Barbolosi
By Luc Bougé
By Gilles Dowek
By François Boisson
By Gérard Berry
By Simon Lacoste-Julien
By Olivier Bournez
By Judicaël Courant
By Frédéric Vivien
By Frédéric Vivien
By Sylvie Boldo
By Gilles Dowek
By Clément Delcamp
By Clément Delcamp
By Giuseppe Savaré
By Ronnie Pavlov
By Tamara Kucherenko
