Exposés de recherche

Collection Exposés de recherche

00:00:00 / 00:00:00
191 380

Algorithmes d'approximation - Partie 2

By Frédéric Vivien

Also appears in collection : Algorithm and programming / Algorithmique et programmation

Dans la deuxième partie de ce cours nous considérerons un problème lié, celui des algorithmes compétitifs. Dans le cadre de l'algorithmique « en-ligne », les caractéristiques d'une instance d'un problème ne sont découvertes qu'au fur et à mesure du traitement de l'instance (comme on ne découvre l'histoire d'un livre qu'au fur et à mesure où on en lit des pages). Ne pas connaître à l'avance toutes les caractéristiques d'une instance interdit souvent - mais pas toujours - de construire un algorithme optimal. Nous montrerons, entre autres, comment utiliser la technique de l'adversaire pour établir une borne inférieure au facteur de compétitivité de tout algorithme en-ligne (cette fois-ci en dehors de toute notion de complexité).

Information about the video

Citation data

  • DOI 10.24350/CIRM.V.18965303
  • Cite this video Vivien, Frédéric (03/05/2016). Algorithmes d'approximation - Partie 2. CIRM. Audiovisual resource. DOI: 10.24350/CIRM.V.18965303
  • URL https://dx.doi.org/10.24350/CIRM.V.18965303

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback