Lecture - 14:15
Leen Stougie - VU University Amsterdam
A decomposition theory for vertex enumeration of convex polyhedra
Abstract:
In the last years the vertex enumeration problem of polyhedra has seen a revival in the study of metabolic networks, which increased the demand for efficient vertex enumeration algorithms for high-dimensional polyhedra given by equalities and inequalities. The complexity of enumeration of vertices of polytopes (bounded polyhedral) is a famous open problem in discrete and computational geometry.
In this paper we do not solve this problem, but present a type of fixed parameter tractable result. We apply the concept of branch-decomposition to the vertex enumeration problem of polyhedra P = {x : Sx = b; x >= 0}. For that purpose, we introduce the concept of k- module and show how it relates to the separators of the linear matroid generated by the columns of S. This then translates structural properties of the matroidal branch-decomposition to the context of polyhedra. We then use this to present a total polynomial time algorithm for polytopes P for which the branch-width of the linear matroid generated by S is bounded by a constant k.
This paper is joint work with Arne Reimers.
Zeit & Ort
04.05.2015 | 14:15
@TU MA 041
www3.math.tu-berlin.de/MDS/index.html