×

The worst-case running time of the random simplex algorithm is exponential in the height. (English) Zbl 0875.90325

Summary: The random simplex algorithm for linear programming proceeds as follows: at each step, it moves from a vertex v of the polytope to a randomly chosen neighbor of v, the random choice being made from those neighbors of v that improve the objective function. We exhibit a polytope defined by n constraints in three dimensions with height O(log n), for which the expected running time of the random simplex algorithm is \(\Omega \)(n/log n).

MSC:

90C05 Linear programming
90C60 Abstract computational complexity for mathematical programming problems
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Dantzig, G. B., Linear Programming and Extensions (1963), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0108.33103
[2] Gärtner, B.; Ziegler, G. M., Randomized simplex algorithms on Klee-Minty cubes, (Proc. 35th Ann. IEEE Symp. on Foundations of Computer Science (1994)), 502-510 · Zbl 0947.90066
[3] Kalai, G.; Kleitman, D. J., A quasi-polynomial bound for the diameter of graphs of polyhedra, Bull. AMS, 26, 315-316 (1992) · Zbl 0751.52006
[4] Kalai, G., A subexponential randomized simplex algorithm, (Proc. 24th Ann. ACM Symp. on Theory of Computing (1992)), 475-482
[5] Klee, V.; Minty, G. J., How good is the Simplex Method, (Sisha, O., Inequalities III (1972), Academic Press: Academic Press New York), 159-175
[6] Todd, M. J., The monotonic bounded Hirsch conjecture is false for dimension at least 4, Math. Oper. Res., 5, 599-601 (1980) · Zbl 0457.52006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.