Thursday, June 20th, 2013 | 4:00pm-5:00pm | Burnside 1205 |

Department of Informatics and Telecommunications, University of Athens

Efficient edge skeleton and volume computation for polytopes
defined by oracles.

In general dimension, there is no known total polynomial algorithm for either convex hull or vertex enumeration, i.e. whose complexity depends polynomially in the input and output sizes. It is thus important to identify polytope constructions for which total polynomial-time algorithms can be obtained.

In the first part of this talk we will discuss a 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. All complexity bounds refer to the (oracle) Turing machine model.

We consider two main applications, where we obtain (weakly) total polynomial-time algorithms: Signed Minkowski sums of convex polytopes, and computation of secondary, resultant, and discriminant polytopes. Further applications include convex combinatorial optimization and convex integer programming.

Finally, we present how polynomial-time Monte Carlo algorithms for volume approximation can be utilized on polytopes given by optimization oracles and briefly discuss our implementation and some first experimental results.

(Joint work with Ioannis Emiris and Bernd Gaertner)