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,...</subscript></subscript></equation>

To solve linear programming problems by interior point methods an approximately centered interior point has to be known. Such a point can be found by an algorithmic approach - a so-called phase 1 algorithm or centering algorithm. For random linear programming problems distributed according to...