Small Shadows of Lattice Polytopes

The diameter of the graph of a d-dimensional lattice polytope P ⊆ [0, k] n is known to be at most dk due to work by Kleinschmidt and Onn. However, it is an open question whether the monotone diameter, the shortest guaranteed length of a monotone path, of a d-dimensional lattice polytope P = x : Ax ≤ b ⊆ [0, k] n is bounded by a polynomial in d and k. This question is of particular interest in linear optimization, since paths traced by the Simplex method must be monotone.

We introduce partial results in this direction including a monotone diameter bound of 3d for k = 2, a monotone diameter bound of (d -1)m + 1 for d-dimensional (m + 1)-level polytopes, a pivot rule such that the Simplex method is guaranteed to take at most dnk||A||∞ non-degenerate steps to solve a LP on P , and a bound of dk for lengths of paths from certain fixed starting points. Finally, we present a constructive approach to a diameter bound of (3/2)dk and describe how to translate this final bound into an algorithm that solves a linear program by tracing such a path.