Abdullahi, Sammani Danwawu (2002) Vertex enumeration and counting for certain classes of polyhedra. PhD thesis, University of Leeds.
Vertex enumeration (VE) algorithms explore the problem of listing some or all solutions that lie at corners of a convex polyhedron defined by a set of linear inequalities. Many algorithms have been developed for general polytopes. The most successful of these, from both an empirical and theoretical viewpoint, are based on pivoting. Dyer  gives an algorithm for simple polytopes which runs in time O (mn^2) per vertex. In this thesis we concentrate on the VE problem for certain special classes of polyhedron. We also address the problem of (approximately) counting the vertices without listing them. Pivoting algorithms rely on the correspondence between vertices and feasible bases and are consequently inefficient in the presence of a high degree of degeneracy such as frequently occurs in network polyhedra. Provan  gives a high-level description of a VE algorithm for such polyhedra which has running time that is quadratic in the number of vertices. W e describe an implementation of Provan's algorithm, present some computational results on transportation and assignment polytopes and discuss some practical difficulties with the algorithm. We then present an algorithmic description of a VE method via the dual Fourier-Motzkin (F-M) elimination method. One of the difficulties with F-M is that the number of constraints introduced in eliminating variables grows exponentially; we show that, for linear inequality systems with at most two variables per constraint, denoted LI(2), the growth is exponential in the number of variables but linear in the number of constraints. We go on to prove results which characterize the basis structure for LI(2) and dual LI(2) systems and hence develop a new pivoting algorithm for enumerating vertices of polyhedra associated with dual LI(2) systems. Counting the vertices of general polyhedra is #P-complete  and thus approximate counting procedures are of interest. In particular, some fpras for counting vertices of polyhedra associated with 0-1 Permanent, Down Sets, Independent Sets, 0-1 Knapsack Problems, 2 by n transportation problems, matroids and matchings in a non-bipartite graph are developed.
|Item Type:||Thesis (PhD)|
|Additional Information:||Supplied directly by the School of Computing, University of Leeds|
|Department:||The University of Leeds > Faculty of Engineering (Leeds) > School of Computing (Leeds)|
|Deposited By:||Dr L G Proll|
|Deposited On:||08 Mar 2011 09:40|
|Last Modified:||08 Mar 2011 09:40|
Repository Staff Only: item control page