Exploring Counting Methods for the Vertices of Certain Polyhedra with Uncertainties

Authors: Sammani Danwawu Abdullahi

Abstract:

Vertex Enumeration Algorithms explore the methods and procedures of generating the vertices of general polyhedra formed by system of equations or inequalities. These problems of enumerating the extreme points (vertices) of general polyhedra are shown to be NP-Hard. This lead to exploring how to count the vertices of general polyhedra without listing them. This is also shown to be #P-Complete. Some fully polynomial randomized approximation schemes (fpras) of counting the vertices of some special classes of polyhedra associated with Down-Sets, Independent Sets, 2-Knapsack problems and 2 x n transportation problems are presented together with some discovered open problems.

Keywords: Approximation, counting with uncertainties, mathematical programming, optimization, vertex enumeration.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1111590

References:

Abdullahi, S. D. (2002) Vertex Enumeration and Counting for Certain Classes of Polyhedra. School of Computing. The University of Leeds.
[2] Dyer, M. E. (1983) The Complexity of Vertex enumeration methods. Mathematics of Operation Research. 8 381 - 402.
[3] Hadley, G. (1962) Linear Programming Addison-Wesley.
[4] Dyer, M. E. (1979) Vertex Enumeration in Mathematical Programming: Methods and Applications. Department of Computer Studies. The University of Leeds.
[5] Jerrum, M. (1995) The computational complexity of counting. International Congress of Mathematicians. Birkhauser, Basel 1995.
[6] Jerrum, M. and Sinclair, A. (1996) The Markov Chain Monte Carlo method: an approach to approximate counting and integration. PWS Publishing, Boston.
[7] Garey, A. M. and Johnson, D. S. (1979) Computers and Intractability Freeman.
[8] Dyer, M. and Greenhil, C. (2000) On Markov Chains for Independent Sets. Journal of Algorithms. 35 17 - 49.
[9] Dyer, M. E., Goldberg, L. A., Greenhill, C. S. and Jerrum, M. R. (2000) On the Relative Complexity of Approximate Counting Problems Springer-Verlag.