English
Algorithmes d'approximation - Partie 1
Post-edited
Auteurs : Vivien, Frédéric (Auteur de la conférence)
CIRM (Editeur )
68Q25 - Analysis of algorithms and problem complexity
68T20 - Problem solving (heuristics, search strategies, etc.)
68W25 - Approximation algorithms
CIRM (Editeur )
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 Vidéo
Réalisateur : Hennenfent, GuillaumeLangue : Français Date de Publication : 19/05/2016 Date de Captation : 03/05/2016 Sous Collection : Research talks Catégorie arXiv : Computer Science Domaine(s) : Informatique Format : MP4 (.mp4) - HD Durée : 01:31:21 Audience : Chercheurs Download : https://videos.cirm-math.fr/2016-05-03_Vivien_part1.mp4 
|
Informations sur la Rencontre
Nom de la Rencontre : Algorithm and programming / Algorithmique et programmationOrganisateurs de la Rencontre : Albert, Luc ; Dorra, Francis ; Petit, Antoine Dates : 02/05/16 - 06/05/16 Année de la rencontre : 2016 URL de la Rencontre : http://conferences.cirm-math.fr/1446.html
Données de citation
DOI : 10.24350/CIRM.V.18965103Citer cette vidéo: 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
- [Multi angle] Calculer avec des équations différentielles : calculabilité, complexité / Auteur de la conférence Bournez, Olivier.
- [Multi angle] Big Data: Tremendous challenges, great solutions / Auteur de la conférence Bougé, Luc.
- [Multi angle] Buffer overflow ou explication de « une faille de type bufferoverflow peut permettre à un code malicieux d'être éxécuté » / Auteur de la conférence Boisson, François.
- [Multi angle] Algorithmes d'approximation - Partie 2 / Auteur de la conférence Vivien, Frédéric.
Bibliographie
