Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm

DOI10.1007/BF01580645MaRDI QIDQ3755229zbMATH OpenFDO

Authors Nimrod Megiddo

Publication date 1986

Published in Mathematical Programming (Search for Journal in Brave)

zbMATH Keywords

spherical symmetryprobabilistic analysisaverage number of stepsself-dual simplex algorithm

Mathematics Subject Classification ID

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

Recommendations

• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• scientific article; zbMATH DE number 3880432
• scientific article; zbMATH DE number 3898607
• The average number of pivot steps of the simplex-algorithm based on a generalized rotation-symmetry-model
• A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only

Cites work

• scientific article; zbMATH DE number 3648423 (Why is no real title available?)
• scientific article; zbMATH DE number 3880432 (Why is no real title available?)
• scientific article; zbMATH DE number 3894831 (Why is no real title available?)
• A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• Bimatrix Equilibrium Points and Mathematical Programming
• Linear Programming in Linear Time When the Dimension Is Fixed
• New Finite Pivoting Rules for the Simplex Method
• New results on the average behavior of simplex algorithms
• On the average number of steps of the simplex method of linear 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
• 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

(12)

• A friendly smoothed analysis of the simplex method
• Parametric linear programming and anti-cycling pivoting rules
• New results on the average behavior of simplex algorithms
• scientific article; zbMATH DE number 3845338 (Why is no real title available?)
• An algorithm for disjunctive programs
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• scientific article; zbMATH DE number 3880432 (Why is no real title available?)
• An asymptotic estimate of the average number of steps of the parametric simplex method
• Upper and lower bounds on the smoothed complexity of the simplex method
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• scientific article; zbMATH DE number 4027159 (Why is no real title available?)
• George Dantzig's impact on the theory of computation

This page was built for publication: Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm

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