Recent Advances in Diameter of Polyhedra

Abstract: The diameter of polyhedra has attracted attention for years due to its connection with the complexity of the simplex algorithm. In particular, giving sharp bounds on the diameter in terms of specified parameters is a central topic in mathematical optimization and computational geometry. In this talk, we will survey some recent results on the diameter of polyhedra with emphasis on those for lattice polytopes. A lattice polytope means a polytope whose vertices are drawn from {0,1,...,k}d (namely, here, k and d are the parameters). It is known since the 1990s that the diameter of lattice polytopes behaves as Θ(k2/3) in dimension 2. We give an explicit expression for the diameter of lattice zonotopes in fixed dimension for infinitely many k, which implies that the diameter of lattice polytopes behaves as Ω(kd/(d+1)) in dimension d. This talk is based on joint work with Antoine Deza and Lionel Pournin.

game theorymachine learningmathematical softwarecomputer science theorycombinatoricsoptimization and control

Audience: researchers in the topic

Mixed Integer Programming Workshop 2021

Series comments: The 18th Mixed Integer Programming Workshop will be held online on May 24-27, 2021.

It will feature 21 distinguished invited speakers covering most aspects of Mathematical Optimization, an interactive, gamified MIP student poster session with 50 posters, and a casual business meeting.

Registration is free of charge. Register here: fico.zoom.us/webinar/register/2416186463858/WN_DVLhGOToQkKyvKYPiA4cQw

Find the website of MIP2021 at sites.google.com/view/mipworkshop2021/.