On the diameter of polytope

Yaguang Yang

Published 2018-09-07Version 1

Bonifas et. al. \cite{bsehn14} derived an upper bound of a polytope $P=\{ x\in \mathbb{R}^n: Ax \le b \}$ where $A \in \mathbb{Z}^{m \times n}$ and $m>n$. This comment indicates that their method can be applied to the case where $A \in \mathbb{R}^{m \times n}$, which results in an upper bound of the diameter for the general polytope $\mathcal{O} \left( \frac{n^3 \Delta}{\det(A^*)} \right)$, where $\Delta$ is the largest absolute value among all $(n-1) \times (n-1)$ sub-determinants of $A$ and ${\det(A^*)}$ is the smallest absolute value among all nonzero $n \times n$ sub-determinants of $A$. For each given polytope, since $\Delta$ and $\det(A^*)$ are fixed, the diameter is bounded by $\mathcal{O}(n^3)$.