ISSN:
1439-6912
Schlagwort(e):
AMS Subject Classification (1991) Classes: 90C05, 52B12, 68Q25
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/PL00009827
Permalink