Broder, Andrei Z.; Dyer, Martin E.; Frieze, Alan M.; Raghavan, Prabhakar; Upfal, Eli The worst-case running time of the random simplex algorithm is exponential in the height. (English) Zbl 0875.90325 Inf. Process. Lett. 56, No. 2, 79-81 (1995). 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). Cited in 6 Documents MSC: 90C05 Linear programming 90C60 Abstract computational complexity for mathematical programming problems 68Q25 Analysis of algorithms and problem complexity Keywords:Linear programming; Algorithms; Simplex algorithm; Randomized algorithm PDFBibTeX XMLCite \textit{A. Z. Broder} et al., Inf. Process. Lett. 56, No. 2, 79--81 (1995; Zbl 0875.90325) 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.