Sammani D. Abdullahi
Born: August 1, 1969
birthplace: Kano, Nigeria
Australian Permanent Residence)
1985-1990 ---BSc Mathematics (1990) Bayero University Kano ; MSc (1996) Bayero University Kano
PhD (2003) Computing (Computer Algorithms) Leeds University U.K.
thesis: Vertex Enumeration and Counting for Certain Classes of Polyhedra ; advisors L G Proll and Martin Dyer
: Mathematics and Information Technology Program Unit,
United Arab Emirates Universitypersonal or universal URL:
email: SammaniA@uaeu.ac.aemail: Mathematics and Information Technology Program Unit, United Arab Emirates University, University General Requirements Unit, P.O.Box 17172, Al-Ain, Abu-Dhabi, United Arab Emirates
Ph.D 2003 Research thesis abstract of Sammani Danwawu Abdullahi
Vertex Enumeration and Counting for Certain Classes of Polyhedra
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 [24] 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 [79] 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 [24] 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.
RESEARCH
On algorithms for geometrical problems in mathematical programming. Vertex enumeration problems and its relatives.
PUBLICATIONS
- S D Abdullahi, M E Dyer, L G Proll "Counting vertices of certain classes of polyhedra" 18th International Symposium on Mathematical Programming to be held on the campus of the Technical University of Denmark Copenhagen, Denmark August 18-22, 2003.
- S D Abdullahi, M E Dyer, L G Proll "Listing vertices of polyhedra associated with dual LI (2) system" DMTCS'03 - Fourth International Conference on Discrete Mathematics and Theoretical Computer Science (Organized by the Université de Bourgogne and CDMTCS - 7 - 12 July 2003, Dijon, France)
- Sammani Abdullahi, Martin Dyer, Les Proll "Enumerating vertices of network Polyhedra" 17th International Symposium on Mathematical Programming, hosted by Georgia Institute of Technology, U.S.A., ISMP 2000, August 7-11, 2000.
- S.D. Abdullahi. "A fast Algorithm for Polyhedra associated with a network L.P structures." Proceedings, International Conference in Mathematical Sciences, Al-Ain, ICM '99, UAE University, Nov. 1999.
- S D Abdullahi, M E Dyer, L G Proll "Vertex Enumeration via Dual F-M method" (To appear).
reference: Dr. Abdullahi's CV;
The web pages
MATHEMATICIANS OF THE
AFRICAN DIASPORA
are brought to you by
The Mathematics Department
of
The State University of New York at Buffalo.
They are created and maintained by
Scott W. Williams
Professor of Mathematics
