| Article ID: | iaor20083425 |
| Country: | Netherlands |
| Volume: | 14 |
| Issue: | 2/3 |
| Start Page Number: | 153 |
| End Page Number: | 164 |
| Publication Date: | Oct 2007 |
| Journal: | Journal of Combinatorial Optimization |
| Authors: | Rothblum Uriel G., Onn Shmuel |
| Keywords: | programming: linear |
Given a list of vectors that contains directions of the edges of a given polytope ℘ and the availability of an algorithm that solves linear programs over ℘, we describe a method for enumerating the vertices of ℘ in particular, the method is adaptable to polytopes which are presented as (linear) projections of polytopes having linear inequality representation. Polynomial complexity bounds under both the real and the binary computation models are derived when the dimension of the polytope is fixed and the given LP algorithm is polynomial.