m

F Nous contacter


0
     
Post-edited

H 2 Algorithmes d’approximation - Partie 1

Auteurs : Vivien, Frédéric (Auteur de la Conférence)
CIRM (Editeur )

Loading the player...
NP-completeness definition of approximation algorithm definition of asymptotic approximation algorithm vertex cover problem bin packing problem travelling salesman problem 2-partition problem questions of the audience

Résumé : 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).

Codes MSC :
68Q25 - Analysis of algorithms and problem complexity
68T20 - Problem solving (heuristics, search strategies, etc.)
68W25 - Approximation algorithms

Informations sur la rencontre

Nom du congrès : Algorithm and programming / Algorithmique et programmation
Organisteurs Congrès : Albert, Luc ; Dorra, Francis ; Petit, Antoine
Dates : 02/05/16 - 06/05/16
Année de la rencontre : 2016
URL Congrès : http://conferences.cirm-math.fr/1446.html

Citation Data

DOI : 10.24350/CIRM.V.18965103
Cite this video as: Vivien, Frédéric (2016). Algorithmes d’approximation - Partie 1. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.18965103
URI : http://dx.doi.org/10.24350/CIRM.V.18965103

Voir aussi

Bibliographie



Z