A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension

DOI10.1145/4221.4222zbMath0634.65044OpenAlexW2117081489MaRDI QIDQ3773194

Nimrod Megiddo, Ilan Adler

Publication date: 1985

Published in: Journal of the ACM (Search for Journal in Brave)

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

zbMATH Keywords

probabilistic analysis of algorithmssimplex algorithmslexicographic pivotingself-dual method

Mathematics Subject Classification ID

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., A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps, Criss-cross methods: A fresh view on pivot algorithms, Exact semidefinite formulations for a class of (random and non-random) nonconvex quadratic programs, Recent developments in information-based complexity, A Friendly Smoothed Analysis of the Simplex Method, George Dantzig's impact on the theory of computation, Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial, New results on the average behavior of simplex algorithms, On the asymptotic average number of efficient vertices in multiple objective linear programming, On the expected number of linear complementarity cones intersected by random and semi-random rays, Average number of iterations of some polynomial interior-point -- algorithms for linear programming, Pivot rules for linear programming: A survey on recent theoretical developments, Globally determining a minimum-area rectangle enclosing the projection of a higher-dimensional set