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]².

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr