scientific article; zbMATH DE number 3880432

MaRDI QIDQ3346084zbMATH OpenFDO

Authors Stephen Smale

Publication date 1983

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)

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
• New results on the average behavior of simplex algorithms
• The simplex method. A probabilistic analysis
• Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm

Cited in

(19)

• Average case optimality
• Homotopy techniques in linear programming
• A simplex variant solving an m 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
• Fast finite methods for a system of linear inequalities
• A note on the distribution of the number of simplex iterations to optimality
• scientific article; zbMATH DE number 3845338 (Why is no real title available?)
• New results on the average behavior of simplex algorithms
• Random linear programs with many variables and few constraints
• Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
• An asymptotic estimate of the average number of steps of the parametric simplex method
• scientific article; zbMATH DE number 4027159 (Why is no real title available?)
• 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
• The 1982 ACM Turing Award lecture. An overview of computational complexity
• On a new iterative algorithm for solving linear equations

This page was built for publication:

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