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

DOI10.1016/0020-0190(95)00101-HMaRDI QIDQ671935zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Andrei Broder, Martin Dyer, Prabhakar Raghavan, Eli Upfal, Alan 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

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

Recommendations

• Exponential upper bounds for the runtime of randomized search heuristics
• STACS 2005
• Exponential bounds for the running time of a selection algorithm
• Randomized rounding for the largest simplex problem
• Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
• scientific article; zbMATH DE number 4027159
• Two New Bounds for the Random‐Edge Simplex‐Algorithm
• A randomized polynomial-time simplex algorithm for linear programming
• A simple expected running time analysis for randomized ``divide and conquer algorithms
• Randomized simplex algorithms on Klee-Minty cubes

Cites work

• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Randomized simplex algorithms on Klee-Minty cubes
• The Monotonic Bounded Hirsch Conjecture is False for Dimension at Least 4

Cited in

(8)

• Lower bounds for a subexponential optimization algorithm
• A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games
• The Simplex Algorithm in Dimension Three
• Random walks on polytopes of constant corank
• Reverse 1-centre problem on trees under convex piecewise-linear cost function
• One line and n points
• The Random‐Facet simplex algorithm on combinatorial cubes
• Random edge can be exponential on abstract cubes

This page was built for publication: The worst-case running time of the random simplex algorithm is exponential in the height

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q671935)