text: Abstract In 1992, Kalai and Kleitman proved that the diameter of a d -dimensional polyhedron with n facets is at most n 2 + log 2 d . In 2014, Todd improved the Kalai–Kleitman bound to ( n − d ) log 2 d . We improve the Todd bound to ( n − d ) − 1 + log 2 d for n ≥ d ≥ 7 , ( n − d ) − 2 + log 2 d for n ≥ d ≥ 37 , and ( n − d ) − 3 + log 2 d + O 1 ∕ d for n ≥ d ≥ 1 .
  @cite_22: We discuss the application of random walks to generating a random basis of a totally unimodular matrix and to solving a linear program with such a constraint matrix. We also derive polynomial upper bounds on the combinatorial diameter of an associated polyhedron.
  @cite_7: 
  @cite_21: In the mid-eighties Tardos proposed a strongly polynomial algorithm for solving linear programming problems for which the size of the coefficient matrix is polynomially bounded in the dimension of the input. Combining Orlin's primal-based modification and Mizuno's use of the simplex method, we introduce a modification of Tardos' algorithm considering only the primal problem and using the simplex method to solve the auxiliary problems. The proposed algorithm is strongly polynomial if the coefficient matrix is totally unimodular and the auxiliary problems are non-degenerate.
  @cite_6: We derive a new upper bound on the diameter of a polyhedron @math P = x ? R n : A x ≤ b , where @math A ? Z m × n . The bound is polynomial in @math n and the largest absolute value of a sub-determinant of @math A , denoted by @math Δ . More precisely, we show that the diameter of @math P is bounded by @math O ( Δ 2 n 4 log n Δ ) . If @math P is bounded, then we show that the diameter of @math P is at most @math O ( Δ 2 n 3.5 log n Δ ) . For the special case in which @math A is a totally unimodular matrix, the bounds are @math O ( n 4 log n ) and @math O ( n 3.5 log n ) respectively. This improves over the previous best bound of @math O ( m 16 n 3 ( log m n ) 3 ) due to Dyer and Frieze (Math Program 64:1---16, 1994).
  @cite_12: We study the simplex method over polyhedra satisfying certain "discrete curvature" lower bounds, which enforce that the boundary always meets vertices at sharp angles. Motivated by linear programs with totally unimodular constraint matrices, recent results of (Discrete Comput. Geom. 52(1):102---115, 2014), Brunsch and Roglin (Automata, languages, and programming. Part I, pp. 279---290, Springer, Heidelberg, 2013), and Eisenbrand and Vempala (http: arxiv.org abs 1404.1568, 2014) have improved our understanding of such polyhedra. We develop a new type of dual analysis of the shadow simplex method which provides a clean and powerful tool for improving all previously mentioned results. Our methods are inspired by the recent work of Bonifas and the first named author (in: Indyk P (ed) Proceedings of the Twenty-Sixth Annual ACM---SIAM Symposium on Discrete Algorithms, pp. 295---314, SIAM, 2015), who analyzed a remarkably similar process as part of an algorithm for the Closest Vector Problem with Preprocessing. For our first result, we obtain a constructive diameter bound of @math O(n2?lnn?) for n-dimensional polyhedra with curvature parameter @math ??(0,1]. For the class of polyhedra arising from totally unimodular constraint matrices, this implies a bound of @math O(n3lnn). For linear optimization, given an initial feasible vertex, we show that an optimal vertex can be found using an expected @math O(n3?lnn?) simplex pivots, each requiring O(mn) time to compute, where m is the number of constraints. An initial feasible solution can be found using @math O(mn3?lnn?) pivot steps.
summary: Another well-studied parameter would be @math which is defined as the largest absolute value of a subdeterminant of the constraint matrix @math associated to a polyhedron. @cite_6 strengthened and extended the Dyer and Frieze upper bound @cite_22 holding for totally unimodular case; i.e., when @math . Complexity analyses based on @math for the shadow vertex algorithm and the primal-simplex based Tardos' algorithm were proposed by Dadush and H " a hnle @cite_12 , and Mizuno, Sukegawa, and Deza @cite_21 @cite_7 , respectively.