Deformed products and maximal shadows of polytopes
Nina Amenta, Günter M. Ziegler · Contemporary mathematics - American Mathematical Society · 1999
We present a construction of deformed products of polytopes that has as special cases all the known constructions of linear programs with "many pivots," starting with the famous Klee-Minty cubes from 1972. Thus we obtain sharp estimates for the following geometric quantities for d-dimensional simple polytopes with at most n facets: ffl the maximal number of vertices on an increasing path, ffl the maximal number of vertices on a "greedy" greatest increase path, and ffl the maximal number of vertices of a 2-dimensional projection. This, equivalently, provides good estimates for the worst-case behaviour of the simplex algorithm on linear programs with these parameters with the worst-possible, the greatest increase, and the shadow vertex pivot rules. The bounds on the maximal number of vertices on an increasing path or a greatest increase path unify and slightly improve a number of known results. One bound on the maximal number of vertices of a 2-dimensional projection is new: we show ...