Worst case behavior of the steepest edge simplex method

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)

zbMATH Keywords

computational complexityupper estimatesimplex algorithmsteepest edge criterionworst case behavior

Mathematics Subject Classification ID

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

• The simplex algorithm with the pivot rule of maximizing criterion improvement
• A practicable steepest-edge simplex algorithm
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item