|
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. |