On the complexity of a pivot step of the revised simplex algorithm

DOI10.1016/0898-1221(85)90190-7MaRDI QIDQ1068713zbMATH OpenOpenAlexFDO

Authors Victor Y. Pan

Publication date 1985

Published in Computers & Mathematics with Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0898-1221(85)90190-7

zbMATH Keywords

stabilityerror analysisbit- complexity estimatesmodification of the revised simplex algorithm

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Linear programming (90C05)

Recommendations

• scientific article; zbMATH DE number 2208706
• scientific article; zbMATH DE number 746214
• A modification of revised simplex method
• A Comparison of the Original and Revised Simplex Methods
• Pivot vector method and its applications

Cites work

• scientific article; zbMATH DE number 3177183 (Why is no real title available?)
• scientific article; zbMATH DE number 3750146 (Why is no real title available?)
• scientific article; zbMATH DE number 3782281 (Why is no real title available?)
• scientific article; zbMATH DE number 192986 (Why is no real title available?)
• scientific article; zbMATH DE number 3497901 (Why is no real title available?)
• scientific article; zbMATH DE number 3624682 (Why is no real title available?)
• scientific article; zbMATH DE number 3454409 (Why is no real title available?)
• scientific article; zbMATH DE number 3892457 (Why is no real title available?)
• scientific article; zbMATH DE number 3892487 (Why is no real title available?)
• scientific article; zbMATH DE number 3363343 (Why is no real title available?)
• scientific article; zbMATH DE number 3408799 (Why is no real title available?)
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• Fast and efficient linear programming and linear least-squares computations
• Fast finite methods for a system of linear inequalities
• Feature Article—The Ellipsoid Method: A Survey
• How to multiply matrices faster
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

Cited in

(12)

• scientific article; zbMATH DE number 746214 (Why is no real title available?)
• A lower bound on the average number of pivot-steps for solving linear programs. Valid for all variants of the simplex-algorithm
• Random projections for linear programming
• Efficient parallel linear programming
• A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only
• On Simplex Pivoting Rules and Complexity Theory
• An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm
• Analysis of algorithms for stable estimation of coefficients of multiple linear regression models
• A note on the Edmonds-Fukuda pivoting rule for simplex algorithms
• Fast and efficient linear programming and linear least-squares computations
• Estimating the probability that a given vector is in the convex hull of a random sample
• Formalization of Incremental Simplex Algorithm by Stepwise Refinement

This page was built for publication: On the complexity of a pivot step of the revised simplex algorithm

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