00:00:00 / 00:00:00

Algorithmes d'approximation - Partie 1

De Frédéric Vivien

Apparaît dans la collection : Algorithm and programming / Algorithmique et programmation

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).

Informations sur la vidéo

Données de citation

  • DOI 10.24350/CIRM.V.18965103
  • Citer cette vidéo Vivien, Frédéric (03/05/2016). Algorithmes d'approximation - Partie 1. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.18965103
  • URL https://dx.doi.org/10.24350/CIRM.V.18965103

Domaine(s)

Dernières questions liées sur MathOverflow

Pour poser une question, votre compte Carmin.tv doit être connecté à mathoverflow

Poser une question sur MathOverflow




Inscrivez-vous

  • Mettez des vidéos en favori
  • Ajoutez des vidéos à regarder plus tard &
    conservez votre historique de consultation
  • Commentez avec la communauté
    scientifique
  • Recevez des notifications de mise à jour
    de vos sujets favoris
Donner son avis