One line and n points

DOI10.1002/rsa.10099zbMath1154.90545OpenAlexW2079716694WikidataQ54310249 ScholiaQ54310249MaRDI QIDQ4446873

Pavel Valtr, Falk Tschirschnitz, Ermo Welzl, Bernd Gärtner, József Solymosi

Publication date: 3 February 2004

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.10099

zbMATH Keywords

linear programmingrandomizationsimplex algorithmrandom-edge pivot rule

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Stochastic programming (90C15) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial probability (60C05)

Related Items

Unique sink orientations of grids ⋮ A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games ⋮ Random Walks on Polytopes of Constant Corank ⋮ Deterministic Algorithms for Unique Sink Orientations of Grids ⋮ The complexity of optimization on grids

Cites Work

• Unnamed Item
• Unnamed Item
• The worst-case running time of the random simplex algorithm is exponential in the height
• Randomized simplex algorithms on Klee-Minty cubes
• Linear programming, the simplex algorithm and simple polytopes
• Entering and leaving \(j\)-facets