ALEXANDER BLACK: Small Shadows of Lattice Polytopes

Seminars - Occasional seminars
Speakers
ALEXANDER BLACK, University of California, Davis
12:00 - 13:00
Room 3-E4-SR03 (Rontgen)
img

Abstract: 

 

For 75 years, the simplex method has remained one of the most popular methods for solving linear programs, yet much still remains mysterious about its performance. Geometrically, the simplex method optimizes a linear function by tracing a path on the oriented graph of a polyhedron, and the simplex method may only run quickly if this graph has small diameter. It is a fundamental open question to understand whether polyhedra are guaranteed to have polynomially bounded diameters. However, even in cases in which we know bounds on diameters, actually following such short paths with the simplex method has continued to be an additional challenge. I will talk a bit about my recent joint work with Jesús De Loera, Sean Kafer, and Laura Sanità on finding pivot rules for the simplex method guaranteed to match the theoretical best possible bound on diameters for 0/1-polytopes as well as my work on nearly matching the best known bounds for lattice polytopes.