• home
• current students
• graduate
• events

Presenter: Dr. David Bremner - Faculty of Computer Science, University of New Brunswick - Faculty Applicant
Supervisor: Dr. Nigel Horspool, Chair, Department of Computer Science

Date: Mon, January 7, 2002
Time: 13:30:00 - 14:30:00
Place: Engineering Office Wing (EOW) Room #430

ABSTRACT

ABSTRACT:

In this talk I will relate some of my recent experience with "experimental Theoretical computer science": the use of computers to tackle mathematical problems that in turn yield insight into the complexity of certain algorithms. A convex polytope is the convex hull of a finite set of points in Rd. Just as in the familiar 2 and 3 dimensional case, convex polytopes in arbitrary dimensions have vertices and edges connecting pairs of vertices, forming the so-called skeleton graph. The well known simplex method of linear programming walks from vertex to vertex along edges, improving the solution at each step. Hirsch conjectured almost 45 years ago that the diameter of the skeleton graph of a d dimensional polytope with n facets is at most (n - d). Since there can be exponentially many vertices in the skeleton graph in terms of the number of facets, this conjecture is quite remarkable, although somewhat supported by the behaviour of the simplex method in practice. As of this writing, the best bound for the skeleton diameter is 2(2d)log2(n), due to Kalai. This large gap motivates the search for polytopes with large diameter, i.e. for counterexamples to the Hirsch Conjecture. Matroid polytopes are a combinatorial generalization of convex polytopes. If the Hirsch conjecture is false for convex polytopes, then it is also false for matroid polytopes. The validity of the Hirsch conjecture for matroid polytopes is also of independent interest. Perhaps most importantly, matroid polytopes provide a discrete search space that is relatively straightforward, if time-consuming, to search. With Klee, Babson, and Holt, I have begun computer-search based investigation of the diameters of matroid polytopes. The general idea is to start with a long path, and search for a (matroid) polytope with this path as the shortest path between two vertices. So far we have developed techniques to enumerate (i.e. generate) combinatorially distinct paths of a certain length and dimension, and I have written two programs to complete matroid polytopes from paths. The first of these programs has been successfully parallelized and runs with almost perfect speedup on clusters of commodity computers. I will survey both practical and theoretical issues related to this project. No specialized background should be necessary on the part of the audience.