On Sub-determinants and the Diameter of Polyhedra

We derive a new upper bound on the diameter of a polyhedron \(P = \{x {\in } {\mathbb {R}}^n :Ax\le b\}\) , where \(A \in {\mathbb {Z}}^{m\times n}\) . The bound is polynomial in \(n\) and the largest absolute value of a sub-determinant of \(A\) , denoted by \(\Delta \) . More precisely, we show that the diameter of \(P\) is bounded by \(O(\Delta ^2 n^4\log n\Delta )\) . If \(P\) is bounded, then we show that the diameter of \(P\) is at most \(O(\Delta ^2 n^{3.5}\log n\Delta )\) . For the special case in which \(A\) is a totally unimodular matrix, the bounds are \(O(n^4\log n)\) and \(O(n^{3.5}\log n)\) respectively. This improves over the previous best bound of \(O(m^{16}n^3(\log mn)^3)\) due to Dyer and Frieze (Math Program 64:1–16, 1994).