Borgwardt, Karl Heinz; Huhn, Petra - In: Computational Statistics 49 (1999) 2, pp. 175-210
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,...
