An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm

DOI10.1145/2746539.2746557zbMath1321.90080OpenAlexW2080654168MaRDI QIDQ2941509

Thomas Dueholm Hansen, Uri Zwick

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2746539.2746557

zbMATH Keywords

linear programmingsimplex algorithmrandomized pivoting rules

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05) Randomized algorithms (68W20)

Related Items

Solving generic nonarchimedean semidefinite programs using stochastic game algorithms ⋮ An exponential lower bound for Zadeh's pivot rule ⋮ The Polyhedral Geometry of Pivot Rules and Monotone Paths ⋮ Inapproximability of shortest paths on perfect matching polytopes ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ Constraint Satisfaction Problems over Numeric Domains ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A space decomposition-based deterministic algorithm for solving linear optimization problems ⋮ A Simplex Method for Countably Infinite Linear Programs ⋮ Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization

Uses Software

• Graphs

Cites Work

• Unnamed Item
• Ramsey partitions and proximity data structures
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On Approximate Distance Labels and Routing Schemes with Affine Stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Approximate distance oracles
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Shortest-path queries in static networks
• Approximate distance oracles with constant query time
• Automata, Languages and Programming