Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 11 juillet 2017 à 14h00 en B107, Lionel Pournin nous parlera de : Sur le diamètre des polytopes en nombres entiers

Résumé : Le diamètre des polyèdres est une borne théorique sur la complexité de l'algorithme du simplexe. Pour cette raison, il est habituellement estimé en fonction de la dimension d du polyèdre et du nombre n de ses facettes. Dans le cas des polytopes en nombres entiers contenus dans l'hypercube [0,k]d, un autre jeu de paramètres qui a du sens est la taille k de l'hypercube cube et sa dimension d. Cet exposé présente des résultats récents sur le plus grand diamètre δ(d,k) de tels polytopes. Plusieurs de ces résultats seront présentés et discutés. Ces résultats seront mis en perspective avec la conjecture de Hirsch (maintenant infirmée) et avec des travaux de Thiele, Balog et Bàràny et Acketa et Žunic sur les polygones en nombres entiers contenus dans le carré [0,k]2.


Dernière modification : jeudi 10 août 2017 Valid HTML 4.01! Valid CSS! Organisateurs : Cyril.Banderier & Gerard.Duchamp at lipn.univ-paris13.fr