New results on the average behavior of simplex algorithms

DOI10.1090/S0273-0979-1984-15317-5zbMath0545.90066OpenAlexW2011643216MaRDI QIDQ3337215

Michael J. Todd, Nimrod Megiddo, Ilan Adler

Publication date: 1984

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0273-0979-1984-15317-5

zbMATH Keywords

average behaviorperformance of simplex algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05)

Related Items

Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure., Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm, Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation, The main vertices of a star set and related graph parameters, On the expected number of linear complementarity cones intersected by random and semi-random rays, Book Review: The basic George B. Dantzig

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• On the average number of steps of the simplex method of linear programming
• Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• Computational complexity of parametric linear programming
• The Average number of pivot steps required by the Simplex-Method is polynomial
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method