scientific article

zbMath0552.90059MaRDI QIDQ3346084

Stephen Smale

Publication date: 1983

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

average speed of the simplex methodself-dual parametric variation of the simplex method

Mathematics Subject Classification ID

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

Related Items

Random linear programs with many variables and few constraints ⋮ Homotopy techniques in linear programming ⋮ A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps ⋮ Average complexity of divide-and-conquer algorithms ⋮ Statistical complexity of the power method for Markov chains ⋮ Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm ⋮ Fast finite methods for a system of linear inequalities ⋮ On the average speed of Lemke's algorithm for quadratic programming ⋮ On the expected number of linear complementarity cones intersected by random and semi-random rays ⋮ Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems ⋮ Random inequality constraint systems with few variables ⋮ On a new iterative algorithm for solving linear equations ⋮ Average case optimality