Accueil/ expose
De la convexité tropicale aux jeux répétés
jeudi 30 janvier 2014

Loading the player...
Descriptif

Conférence de Stéphane Gaubert dans le cadre du séminaire général d'informatique.

Une question aussi ancienne que la programmation linéaire consiste à trouver une règle de pivotage pour l'algorithme du simplexe conduisant à un nombre polynomial d'opérations.
Une autre question consiste à trouver un algorithme résolvant en temps polynomial un jeu répété déterministe dont la valeur est définie comme un paiement moyen par unité de temps. Sans résoudre aucune de ces deux questions, nous montrons qu'une réponse positive à la première entraînerait une réponse positive à la seconde, pourvu que la règle de pivotage satisfasse certaines conditions.
La preuve de ce résultat fait appel à la convexité tropicale et nous servira de prétexte à faire une introduction à celle-ci.
Cet exposé est basé sur un travail avec Akian et Guterman (arXiv:0912.2462, IJAC 2012) ainsi que sur un travail avec Allamigeon, Benchimol, et Joswig arXiv:1308.0454, arXiv:1309.5925)

Voir aussi


  • Aucun exposé du même auteur.
  • Recent Progress in Leakage-Resilient Cry...
    Yevgeniy Dodis
  • Composer le temps
    Gérard Berry
  • Approximation Bounds for Sparse Principa...
    Alexandre D’Aspremont
  • Diviser-pour-Régner & Inférence Statisti...
    Michael I. Jordan
  • Logarithmes discrets dans les corps fini...
    Antoine Joux
  • Une théorie de l'information mentale
    Claude Berrou
  • Exponential Mechanism for Social Welfar...
    Sampath Kannan
  • Untangling knots using combinatorial opt...
    Benjamin Burton
  • A Foundation for Flow-Based Program Matc...
    Julia Lawall
  • Comment faire confiance à un compilateu...
    Xavier Leroy
  • Construction à large couverture de la re...
    Benoît Crabbé
  • Définir et mesurer la complexité : la t...
    Jean-Paul Delahaye
  • Rendre la virgule flottante plus rigoure...
    Jean-Michel Muller
  • Approximations for stochastic graph rewr...
    Vincent Danos
  • Social Networks : a research vision and ...
    Peter Marbach
  • Three discrete geometric structures and ...
    Nabil Mustafa
  • From spanners to distance oracles and co...
    Laurent Viennot
  • Cognitive Computing
    Jérôme Pesenti
  • Vers les nouvelles bases de données pers...
    Serge Abiteboul
  • Structured Parallel Programming Primitiv...
    Vivek Sarkar
  • Manipuler les réseaux euclidiens
    Damien Sthelé
  • Réduction de modèles de voies de signali...
    Jérôme Feret
  • Le patient numérique personnalisé
    Nicholas Ayache
  • Scade 6: conception d'un langage de prog...
    Bruno Pagano
  • Co-Adaptive Instruments. Can we reinven...
    Wendy Mackay
  • Analyse de pire temps d’exécution et pro...
    Pascal Raymond
  • Chiffrer mieux pour (dé)chiffrer plus
    Anne Canteaut
  • New Results at the Crossroads of Convexi...
    Sébastien Bubeck
Auteur(s)
Stéphane Gaubert
École Polytechnique
Professeur

Plus sur cet auteur
Voir la fiche de l'auteur

Cursus :

Stéphane Gaubert est professeur au département de mathématiques appliquées à l'École polytechnique.

Cliquer ICI pour fermer
Annexes
Téléchargements :
   - Télécharger la vidéo
   - Télécharger l'audio (mp3)

Dernière mise à jour : 11/02/2021