Combinatorial Optimization & Graph Algorithms group (COGA)1996

### Page Content

Citation key Report-502-1996 Nina Amenta \and Günter M.Ziegler 1996 502 Technische Universität Berlin, Institut für Mathematik 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: \beginitemize \item the maximal number of vertices on an increasing path, \item the maximal number of vertices on a greedy'' greatest increase path, and \item the maximal number of vertices of a $2$-dimensional projection. \enditemize 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 that a $2$-dimensional projection of a $d$-dimensional polytope with $n$ facets may have as many as $\Theta(n^d/2\rfloor)$ vertices for fixed $d$. This provides the same bound for the worst-case behaviour of the simplex algorithm with the shadow vertex pivot rule. The maximal complexity of shadows in fixed dimension is also relevant for problems of Computational Geometry. We give a new algorithm for the construction of the shadow of a $d$-dimensional polytope. However, we find that for even $d\ge4$ the polars of cyclic polytopes, $C_d(n)\pol$, which have the maximal number of vertices for any given $n$, do not maximize the shadow: for example, any $2$-dimensional projection of $C_4(n)\pol$ has not more than $3n$ vertices. Preprint