Randomized simplex algorithms on Klee-Minty cubes.
Please always quote using this URN: urn:nbn:de:0297-zib-1370
- We investigate the behavior of randomized simplex algorithms on special linear programs. For this, we develop combinatorial models for the Klee-Minty cubes and similar linear programs with exponential decreasing paths. The analysis of two 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.
Download full text files
Additional Services
| Author: | Bernd Gärtner, Günter M. Ziegler |
|---|---|
| Document Type: | ZIB-Report |
| Date of first Publication: | 1994/03/17 |
| Series (Serial Number): | ZIB-Report (SC-94-07) |
| ZIB-Reportnumber: | SC-94-07 |
| Published in: | Appeared in: Proc. 35th Annual Symposium on Foundations of Computer Science (FOCS), Nov. 20-22, 1994, Santa Fe, NM. IEEE Computer Society Press, 1994, pp. 502-510 |
