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:<Equation ID="Equ1"> <EquationSource Format="TEX"/> </Equation> We assume these problems to be randomly generated according to the Rotation-Symmetry-Model: *Let a <Subscript>1</Subscript>,…,a <Subscript>m</Subscript>, v be distributed independently, identically and symmetrically under rotations on ℝ<Superscript>n</Superscript>\{0}. We concentrate on distributions over ℝ<Superscript>n</Superscript> 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 <Subscript>0</Subscript> of the feasible region – if there is any. In Phase II it starts at x <Subscript>0</Subscript> to generate a sequence of vertices x <Subscript>0</Subscript>,… ,x <Subscript>s</Subscript> such that successive vertices are adjacent and that the objective v <Superscript>T</Superscript> x <Subscript>i</Subscript> increases. The sequence ends at a vertex x <Subscript>s</Subscript> 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 <Superscript>var</Superscript> for a variant, when m inequalities and n variables are present, satisfies<Equation ID="Equ2"> <EquationSource Format="TEX"/> </Equation> This result holds, if the selection of x <Subscript>0</Subscript> in Phase I has been done independently of the objective v. Copyright Springer-Verlag Berlin Heidelberg 1999