Generating vertices of polyhedra and related problems of monotone generation
Endre Boros, Khaled Elbassioni, Vladimir A. Gurvich, Kazuhisa Makino · CRM proceedings & lecture notes · 2009
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 in different areas.We consider four such techniques and give examples where they are applicable to vertex enumeration.We also discuss their limitations and sketch an NP-hardness proof for generating the vertices of general polyhedra.