Upper bounds for the diameter and height of graphs of convex polyhedra (Q1196197)

A well-known conjecture of Hirsch related to the complexity of the simplex algorithm for linear programming is that the diameter of the edge-graph of a convex polyhedron is bounded above by a linear function of its dimension \(d\) and number of facets \(n\). However, no bound is known which is even polynomial in \(d\). In fact, this paper exhibits the first quasipolynomial upper bound for the diameter as \(n^{2\log d+3}\). It is also shown that the height, i.e. maximal length of a shortest path along which an objective function is nondecreasing, is logarithmically bounded above by \(2(\sqrt n)\log n\). Although this result does not necessarily lead to a simplex pivoting rule with subexponential behaviour, the author announces such an, as yet unpublished, algorithm. Finally it is shown that both the diameter and the height of any \(d\)- polytope, in which any \(k\)-face has at most \(rk\) facets with \(r\) at least 2, are polynomial in \(d\). Examples of such polyhedra are the feasible sets of generalized flow problems.