New results on the average behavior of simplex algorithms

DOI10.1090/S0273-0979-1984-15317-5MaRDI QIDQ3337215zbMATH OpenOpenAlexFDO

Authors Ilan Adler, Nimrod Megiddo, Michael J. Todd

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

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

Recommendations

• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• A simplex variant solving an m d linear program in O(min(m 2,d 2)) expected number of pivot steps
• scientific article; zbMATH DE number 4197740
• The simplex method. A probabilistic analysis
• scientific article; zbMATH DE number 3880432

Cites work

• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• A simplex variant solving an m d linear program in O(min(m 2,d 2)) expected number of pivot steps
• Computational complexity of parametric linear programming
• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3637614 (Why is no real title available?)
• scientific article; zbMATH DE number 3894831 (Why is no real title available?)
• Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
• On the average number of steps of the simplex method of linear programming
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
• The Average number of pivot steps required by the Simplex-Method is polynomial

Cited in

(17)

• The simplex method. A probabilistic analysis
• A simplex variant solving an m d linear program in O(min(m 2,d 2)) expected number of pivot steps
• Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial
• Adjacent vertex simplex algorithms: More experimental results on random problems
• Interior-point methods: Worst case and average case analysis of a phase-I algorithm and a termination procedure.
• The main vertices of a star set and related graph parameters
• How fast does the simplex method usually work? Or: the search for (stochastic) independence
• A note on the distribution of the number of simplex iterations to optimality
• scientific article; zbMATH DE number 3880432 (Why is no real title available?)
• Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
• scientific article; zbMATH DE number 4027159 (Why is no real title available?)
• Empirical Studies on the Average Efficiency of Simplex Variants under Rotation Symmetry
• On the expected number of linear complementarity cones intersected by random and semi-random rays
• scientific article; zbMATH DE number 764392 (Why is no real title available?)
• Book Review: The basic George B. Dantzig
• Mathematical decision-making with linear and convex programming
• Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

This page was built for publication: New results on the average behavior of simplex algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3337215)