Small Shadows of Lattice Polytopes

DOI10.1137/1.9781611977554.CH63MaRDI QIDQ6396922zbMATH OpenFDO

Authors

Publication date 19 April 2022

Full work available at URL https://doi.org/10.1137/1.9781611977554.CH63

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Abstract: The diameter of the graph of a $d$-dimensional lattice polytope $Psubseteq[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=mathbfx:Amathbfxleqmathbfbsubseteq[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|{|}_{infty}$ 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.

Cited in

(2)

• Exponential lower bounds for many pivot rules for the simplex method
• Upper and lower bounds on the smoothed complexity of the simplex method

This page was built for publication: Small Shadows of Lattice Polytopes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6396922)