Randomized simplex algorithms on Klee-Minty cubes
From MaRDI portal
Publication:1307309
DOI10.1007/PL00009827zbMath0947.90066MaRDI QIDQ1307309
Martin Henk, Bernd Gärtner, Günter M. Ziegler
Publication date: 31 October 1999
Published in: Combinatorica (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Linear programming (90C05)
Related Items
A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations, The Random‐Facet simplex algorithm on combinatorial cubes, A double-pivot simplex algorithm and its upper bounds of the iteration numbers, The worst-case running time of the random simplex algorithm is exponential in the height, 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, Unnamed Item, One line and n points
