TY - JFULL
AU - Sammani Danwawu Abdullahi
PY - 2016/3/
TI - Exploring Counting Methods for the Vertices of Certain Polyhedra with Uncertainties
T2 - International Journal of Mathematical, Computational, Physical, Electrical and Computer Engineering
SP - 63
EP - 67
EM - SammaniA@qu.edu.qa
VL - 10
SN - 1307-6892
UR - http://waset.org/publications/10003676
PU - World Academy of Science, Engineering and Technology
NX - International Science Index 110, 2016
N2 - 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.
ER -