Français
Algorithmes d'approximation - Partie 1
Post-edited
Authors : Vivien, Frédéric (Author of the conference)
CIRM (Publisher )
68Q25 - Analysis of algorithms and problem complexity
68T20 - Problem solving (heuristics, search strategies, etc.)
68W25 - Approximation algorithms
CIRM (Publisher )
Abstract :
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).
MSC Codes : 68Q25 - Analysis of algorithms and problem complexity
68T20 - Problem solving (heuristics, search strategies, etc.)
68W25 - Approximation algorithms
|
Information on the Video
Film maker : Hennenfent, GuillaumeLanguage : French Available date : 19/05/2016 Conference Date : 03/05/2016 Subseries : Research talks arXiv category : Computer Science Mathematical Area(s) : Computer Science Format : MP4 (.mp4) - HD Video Time : 01:31:21 Targeted Audience : Researchers Download : https://videos.cirm-math.fr/2016-05-03_Vivien_part1.mp4 
|
Information on the Event
Event Title : Algorithm and programming / Algorithmique et programmationEvent Organizers : Albert, Luc ; Dorra, Francis ; Petit, Antoine Dates : 02/05/16 - 06/05/16 Event Year : 2016 Event URL : http://conferences.cirm-math.fr/1446.html
Citation Data
DOI : 10.24350/CIRM.V.18965103Cite 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 |
See Also
- [Multi angle] Calculer avec des équations différentielles : calculabilité, complexité / Author of the conference Bournez, Olivier.
- [Multi angle] Big Data: Tremendous challenges, great solutions / Author of the conference Bougé, Luc.
- [Multi angle] Buffer overflow ou explication de « une faille de type bufferoverflow peut permettre à un code malicieux d'être éxécuté » / Author of the conference Boisson, François.
- [Multi angle] Algorithmes d'approximation - Partie 2 / Author of the conference Vivien, Frédéric.
Bibliography
