DIMACS TR: 2007-03

Generating vertices of polyhedra and related monotone generation problems



Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Kazuhisa Makino

ABSTRACT

The well-known vertex enumeration problem calls for generating all vertices of a polyhedron given by its description as a system of linear inequalities. Recently, a number of combinatorial techniques have been developed and applied successfully to a large number of monotone generation problems from different areas. We consider several such techniques and give examples in which they are applicable to vertex enumeration. We also discuss their limitations and suggest methods to prove NP-hardness of a monotone generation problem, in particular, of vertex enumeration for (unbounded) polyhedra.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2007/2007-03.pdf
DIMACS Home Page