Randomized Simplex Algorithms on Klee-Minty Cubes
Bernd Gärtner (joint work with Günter Ziegler)
Institut für Informatik
Freie Universität Berlin
email: gaertner@inf.fu-berlin.de
Report B 94-13
May 94
Get the report here or by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-94-13.ps.gz
We investigate the behavior of randomized simplex algorithms
on special linear programs.
For this, we develop combinatorial models for the
Klee-Minty cubes \cite{KM} and similar
linear programs with exponential decreasing paths.
The analysis of two most natural randomized pivot rules
on the Klee-Minty cubes leads to
(nearly) quadratic lower bounds for the complexity of
linear programming with random pivots. Thus, we disprove two bounds
conjectured in the literature.
At the same time, we establish quadratic upper bounds
for random pivots on the linear programs under investigation.
This motivates the question whether some randomized pivot rules
possibly have quadratic worst-case behavior on
general linear programs.