Estimating the Number of Vertices in Convex Polytopes
Estimating the Number of Vertices in Convex Polytopes
Estimating the number of vertices of a convex polytope defined by a system of linear inequalities is crucial for bounding the run-time of exact generation methods. It is not easy to achieve a good estimator, since this problem belongs to the #P complexity class. In this paper we present two …