Springe direkt zu Inhalt

Lecture by Lionel Pournin (Université Paris 13): Recent results on the diameter of lattice polytopes

Feb 10, 2020 | 02:15 PM

Several new results about the largest possible diameter of a lattice polytope contained in the hypercube [0,k]^d, a quantity related to the complexity of the simplex algorithm, will be presented. Upper bounds on this quantity have been known for a couple of decades and have been improved recently. In this lecture, conjecturally sharp lower bounds on this quantity will be presented for all d and k, as well as exact asymptotic estimates when d is fixed and k grows large. These lower bounds are obtained by computing the largest diameter a lattice zonotope contained in the hypercube [0,k]^d can have, answering a question by Günter Rote. This talk is based on joint work with Antoine Deza and Noriyoshi Sukegawa.

Time & Location

Feb 10, 2020 | 02:15 PM

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)