SODA Conference 2023 Conference Paper
Small Shadows of Lattice Polytopes
- Alexander E. Black
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: A x ≤ 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 3 d for k = 2, a monotone diameter bound of ( d — 1) m + 1 for d -dimensional (ℓ + 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.