DOI: 10.5176/2251-1938_ORS16.25
Authors: Robert Salomone, Radislav Vaisman and Dirk Kroese
Abstract:
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 randomized algorithms for estimating the number of vertices in polytopes. The first is based on the well-known Multilevel Splitting technique. The second, called Stochastic Enumeration, is an improvement of Knuth’s backtrack algorithm. Both methods are shown to bring a significant variance reduction, and outperform the current stateof- the-art in test cases.
Keywords: Multilevel Splitting, Stochastic Enumeration, Rare Events, Vertex Counting, Backtrack Trees
Updating...