TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1996

COGA 5-Wheel

Page Content

to Navigation

Preprints 1996

Deformed Products and Maximal Shadows of Polytopes
Citation key Report-502-1996
Author Nina Amenta \and Günter M.Ziegler
Year 1996
Number 502
Institution Technische Universität Berlin, Institut für Mathematik
Abstract 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.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe