The combinatorial diameter of general polytopes is a major open problem in polyhedral combinatorics. Even for such simple polytopes as the transportation polytope it is unknown. Recently, important steps have been made in this respect on which we wish to proceed. Related to this is the design of strongly polynomial time primal simplex algorithms for the transportation problem.
Counting vertices of polyhedra, given their description in terms of linear constraints, is very hard in general, but also for polytopes like the transportation polytope. In the late eighties a method has been devised to count such objects approximately through exploiting the relation between counting and uniform sampling. Along this line we aim to count vertices of transportation- and related polytopes. Recently, success has been obtained for the transportation polytope under the assumption that either the number of supply points or the number of demand points is fixed. The recent results on the diameter of the transportation polytope suggest that we may relax this condition.
The problems on general polytopes and the question if a strongly polynomial algorithm for linear programming exists are formulated in this project, whose success is not dependent on finding answers to these questions.
Supervisors:
Prof. Bert Gerards (TU Eindhoven / CWI).
Dr. Leen Stougie (TU Eindhoven / CWI).