ISSN:
1439-6912
Keywords:
AMS Subject Classification (1991) Classes: 90C05, 52B12, 68Q25
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
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 (for the expected running time of the random-edge simplex algorithm on Klee-Minty cubes) conjectured in the literature. At the same time, we establish quadratic upper bounds for the expected length of a path for a simplex algorithm with random pivots on the classes of linear programs under investigation. In contrast to this, we find that the average length of an increasing path in a Klee-Minty cube is exponential when all paths are taken with equal probability.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/PL00009827
