The Random‐Facet simplex algorithm on combinatorial cubes
From MaRDI portal
Publication:4537627
DOI10.1002/rsa.10034zbMath1017.68159MaRDI QIDQ4537627
Publication date: 1 July 2002
Published in: Random Structures & Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/rsa.10034
68W20: Randomized algorithms
Related Items
Unnamed Item, Unique End of Potential Line, An exponential lower bound for Cunningham's rule, Unique sink orientations of grids, Unique end of potential line, A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations, Pivoting in linear complementarity: Two polynomial-time cases
Cites Work
- Unnamed Item
- The worst-case running time of the random simplex algorithm is exponential in the height
- Completely unimodal numberings of a simple polytope
- Randomized simplex algorithms on Klee-Minty cubes
- Linear programming, the simplex algorithm and simple polytopes
- Convex and linear orientations of polytopal graphs
- A subexponential bound for linear programming
- The simplex algorithm with the pivot rule of maximizing criterion improvement
- Lower bounds for a subexponential optimization algorithm
- Lectures on Polytopes