The Average number of pivot steps required by the Simplex-Method is polynomial

TLDR

The study examines the average number of pivot steps needed by the Simplex method to solve linear programming problems with m inequality constraints in n variables. Assuming the bounding hyperplanes are independently, identically, and rotationally symmetric, the authors analyze a variant called the Schatteneckenalgorithmus. They show that this variant can compute a starting vertex and that the expected number of pivot steps—and thus the average computation time—is bounded by a polynomial in m and n.

Abstract

The paper deals with the average number of pivot steps required by the Simplex-Method for solving linear programming problems withm inequality-restrictions inn variables. Them hyperplanes bounding the feasible regions of the corresponding inequalities are assumed to be distributed independently, identically and symmetrically under rotations in then-dimensional Euclidean space. A certain variant of the Simplexalgorithm, the so-called Schatteneckenalgorithmus, is analyzed. This variant can even be used for the calculation of a start vertex. For the expected number of pivot steps required for the solution of the programming problem an explicit upper bound, which is polynomial inm andn, can be derived. This result implies that the average computation-time required for solving the problem is polynomial inm andn, too.