The worst-case running time of the random simplex algorithm is exponential in the height

DOI10.1016/0020-0190(95)00101-HzbMath0875.90325OpenAlexW2054252354WikidataQ56324060 ScholiaQ56324060MaRDI QIDQ671935

Martin Dyer, Andrei Z. Broder, Eli Upfal, Prabhakar Raghavan, Alan M. Frieze

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(95)00101-h

zbMATH Keywords

AlgorithmsLinear programmingRandomized algorithmSimplex algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items

Reverse 1-centre problem on trees under convex piecewise-linear cost function, The Random‐Facet simplex algorithm on combinatorial cubes, A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games, Random edge can be exponential on abstract cubes, Random Walks on Polytopes of Constant Corank, One line and n points

Cites Work

• Unnamed Item
• Unnamed Item
• Randomized simplex algorithms on Klee-Minty cubes
• The Monotonic Bounded Hirsch Conjecture is False for Dimension at Least 4
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra