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

DOI10.1016/0020-0190(95)00101-HzbMATH Open0875.90325DBLPjournals/ipl/BroderDFRU95OpenAlexW2054252354WikidataQ56324060 ScholiaQ56324060MaRDI QIDQ671935FDOQ671935

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The Monotonic Bounded Hirsch Conjecture is False for Dimension at Least 4
• A quasi-polynomial bound for the diameter\\of graphs of polyhedra
• Randomized simplex algorithms on Klee-Minty cubes

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)