A lower bound on the average number of Pivot-steps for solving linear programs Valid for all variants of the Simplex-Algorithm

In this paper we derive a lower bound on the average complexity of the Simplex-Method as a solution-process for linear programs (LP) of the type: We assume these problems to be randomly generated according to the Rotation-Symmetry-Model: *Let a 1 ,…,a m , v be distributed independently, identically and symmetrically under rotations on ℝ n \{0}. We concentrate on distributions over ℝ n with bounded support and we do our calculations only for a subfamily of such distributions, which provides computability and is representative for the whole set of these distributions. The Simplex-Method employs two phases to solve such an LP. In Phase I it determines a vertex x 0 of the feasible region – if there is any. In Phase II it starts at x 0 to generate a sequence of vertices x 0 ,… ,x s such that successive vertices are adjacent and that the objective v T x i increases. The sequence ends at a vertex x s which is either the optimal vertex or a vertex exhibiting the information that no optimal vertex can exist. The precise rule for choosing the successor-vertex in the sequence determines a variant of the Simplex-Algorithm. We can show for every variant, that the expected number of steps s var for a variant, when m inequalities and n variables are present, satisfies This result holds, if the selection of x 0 in Phase I has been done independently of the objective v. Copyright Springer-Verlag Berlin Heidelberg 1999