Worst case behavior of the steepest edge simplex method
From MaRDI portal
Publication:1134626
DOI10.1016/0166-218X(79)90004-0zbMath0423.90044MaRDI QIDQ1134626
Donald Goldfarb, William Y. Sit
Publication date: 1979
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05)
Related Items
A new family of exponential LP problems, An exponential lower bound for Zadeh's pivot rule, Inapproximability of shortest paths on perfect matching polytopes, An exponential example for Terlaky's pivoting rule for the criss-cross simplex method, A Friendly Smoothed Analysis of the Simplex Method, A double-pivot simplex algorithm and its upper bounds of the iteration numbers, Constraint Satisfaction Problems over Numeric Domains, A Subexponential Lower Bound for Zadeh’s Pivoting Rule for Solving Linear Programs and Games, On scaling linear programs—some experimental results, Complexity of the gravitational method for linear programming, Steepest-edge rule and its number of simplex iterations for a nondegenerate LP, An efficient simplex type algorithm for sparse and dense linear programs., Practical finite pivoting rules for the simplex method, Fast finite methods for a system of linear inequalities, The ellipsoid method and its implications, On the Length of Monotone Paths in Polyhedra, Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization, The Average number of pivot steps required by the Simplex-Method is polynomial
Cites Work
