The Random‐Facet simplex algorithm on combinatorial cubes

DOI10.1002/rsa.10034zbMath1017.68159OpenAlexW2128694402MaRDI QIDQ4537627

Bernd Gärtner

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

zbMATH Keywords

random-facet algorithm

Mathematics Subject Classification ID

Randomized algorithms (68W20)

Related Items

A complexity analysis of policy iteration through combinatorial matrices arising from unique sink orientations ⋮ Pivoting in linear complementarity: Two polynomial-time cases ⋮ Unique end of potential line ⋮ Realizability makes a difference: a complexity gap for sink-finding in USOs ⋮ Unique sink orientations of grids ⋮ An exponential lower bound for Cunningham's rule ⋮ Unnamed Item ⋮ Unique End of Potential Line

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

This page was built for publication: The Random‐Facet simplex algorithm on combinatorial cubes