A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps

DOI10.1016/0885-064X(87)90007-0zbMath0641.65054OpenAlexW2021495277WikidataQ60307346 ScholiaQ60307346MaRDI QIDQ1100853

Ilan Adler, Ron Shamir, Richard M. Karp

Publication date: 1987

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0885-064x(87)90007-0

zbMATH Keywords

complexitysimplex methodexpected number of pivot stepsparametric constraint-by-constraint algorithm

Mathematics Subject Classification ID

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

Related Items (10)

Revisiting compressed sensing: exploiting the efficiency of simplex and sparsification methods ⋮ Parametric linear programming and anti-cycling pivoting rules ⋮ Clusters with minimum transportation cost to centers: a case study in corn production management ⋮ Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ George Dantzig's impact on the theory of computation ⋮ New results on the average behavior of simplex algorithms ⋮ Geometry of the Gass-Saaty parametric cost LP algorithm ⋮ Average number of iterations of some polynomial interior-point -- algorithms for linear programming ⋮ On the complexity of a pivot step of the revised simplex algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• The simplex algorithm with the pivot rule of maximizing criterion improvement
• On the average number of steps of the simplex method of linear programming
• 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
• A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• The Average number of pivot steps required by the Simplex-Method is polynomial
• Random polytopes: Their definition, generation and aggregate properties
• Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method

This page was built for publication: A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps