DIMACS TR: 94-48

On the Diameter of Polyhedra Associated with Network Optimization

Author: Fred J. Rispoli


Investigations of the diameter of convex polyhedra are motivated by a n effort to understand the complexity of polyhedral edge-following algorithms such as the simplex method. Such studies are especially relevant for many network optimization problems since the simplex method is often used when solving these problems. In this paper a survey is given on the diameter of the polyhedra that arise in well known network optimization problems.

Paper only.
DIMACS Home Page