Linear programs (LPs) are, without any doubt, at the core of both the theory and the practice of mondern applied and computational Optimization (e.g., in discrete optimization LPs are used in practical computations using branch-and-bound, and in approximation algorithms, e.g., in rounding schemes). At the same time  Dantzig’s Simplex method is one of the most famous algorithms to solve LPs and SIAM elected it as one of the top 10 most influential algorithms of the 20th Century.

But despite its key importance, many simple easy-to-state mathematical properties of the Simplex method and its geometry remain unknown. The geometry of the simplex method is very much the convex-combinatorial geometry of polyhedra (e.g., cubes, simplices, etc). Perhaps the most famous geometric-combinatorial challenge is to determine a worst-case upper bound for the graph diameter of polyhedra.  Although a lot of progress has been made, today even for the most elementary textbook linear programs we remain ignorant as to what the exact diameter upper bounds are. In this talk, I will discuss this  geometric problem and present the key ideas for proving that the diameter of graphs of all network-flow polytopes satisfy the Hirsch linear bound. This is joint work with S. Borgwardt (Univ of Colorado) and E. Finhold (Fraunhofer Institut).