abstract
In general dimension, there is no known total polynomial algorithm for
either convex hull or vertex enumeration, i.e. an algorithm whose
complexity depends polynomially on the input and output sizes. It is
thus important to identify problems and polytope representations for
which total polynomial-time algorithms can be obtained. We offer the
first total polynomial-time algorithm for computing the edge-skeleton
- including vertex enumeration - of a polytope given by an
optimization or separation oracle, where we are also given a superset
of its edge directions. We also offer a space-efficient variant of our
algorithm by employing reverse search. All complexity bounds refer to
the (oracle) Turing machine model. There is a number of polytope
classes naturally defined by oracles; for some of them neither vertex
nor facet representation is obvious. We consider two main
applications, where we obtain (weakly) total polynomial-time
algorithms: Signed Minkowski sums of convex polytopes, where polytopes
can be subtracted provided the signed sum is a convex polytope, and
computation of secondary, resultant, and discriminant
polytopes. Further applications include convex combinatorial
optimization and convex integer programming, where we offer a new
approach, thus removing the complexity's exponential dependence in the
dimension.

Back to the publications page