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

DOI10.1016/0898-1221(85)90190-7zbMath0582.90066OpenAlexW1987398890MaRDI QIDQ1068713

Pan, Victor Y.

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)

Related Items (5)

Analysis of Algorithms for Stable Estimation of Coefficients of Multiple Linear Regression Models ⋮ Estimating the probability that a given vector is in the convex hull of a random sample ⋮ Fast and efficient linear programming and linear least-squares computations ⋮ Random Projections for Linear Programming ⋮ Efficient parallel linear programming

Cites Work

• How to multiply matrices faster
• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• Fast finite methods for a system of linear inequalities
• Fast and efficient linear programming and linear least-squares computations
• Feature Article—The Ellipsoid Method: A Survey
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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