DIMACS TR: 2007-03
Generating vertices of polyhedra and related monotone generation problems
Authors: Endre Boros, Khaled Elbassioni, Vladimir Gurvich and Kazuhisa Makino
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:
DIMACS Home Page