Home | People | Seminar | Conferences | Resources


Title: The d-step conjectures

Abstract:For a general linear system consisting of n linear inequalities on d variables, the set of possible solutions is a d-dimensional polyhedron with n facets. If this figure is bounded, we call it a d-polytope with n facets.

In optimizing a linear objective function over this d-polytope, the simplex method moves from vertex to vertex along edges, and so the maximum edge diameter of d-polytopes with n facets provides a bound on the performance of the simplex method under the best selection of edges to follow.

In 1957 W.M.Hirsch conjectured that every d-polytope with n facets has edge diameter at most n-d. It suffices to consider the case n=2d, which includes the cubes for example. In this special case of dimension d and 2d facets, the d-step conjecture states that each pair of vertices is connected by a path of length at most d.

We will take a survey of the d-step conjecture and its relatives, introducing the language and concepts that have proven most fruitful in recent research, and indicating the directions current research seems to be heading.

Return to the seminar page.

Home | People | Seminar | Conferences | Resources

Please send comments about this page to Maurice Rojas at rojas@math.tamu.edu.
Last Modified on 05/Feb/01