zbMATH — the first resource for mathematics

The complexity of vertex enumeration methods. (English) Zbl 0531.90064
Summary: The computational complexity of problems relating to the enumeration of all the vertices of a convex polyhedron defined by linear inequalities is examined. Several published approaches are evaluated in this light. A new algorithm is described, and shown to have a better complexity estimate than existing methods. Empirical evidence supporting the theoretical superiority is presented. Finally vertex enumeration is discussed when the space containing the polyhedra is of fixed dimension and only the size of the inequality system is permitted to vary.

90C05 Linear programming
52Bxx Polytopes and polyhedra
68Q25 Analysis of algorithms and problem complexity
90C08 Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.)
15A39 Linear inequalities of matrices
Full Text: DOI