An exponential example for Terlaky's pivoting rule for the criss-cross simplex method
From MaRDI portal
(Redirected from Publication:911455)
This paper shows that the required number of iterations for Terlaky's pivoting rule for the criss-cross simplex method [see \textit{E. Klafszky} and \textit{T. Terlaky}, Alkalmazott Mat. Lapok 12, 1-14 (1986; Zbl 0631.90039)] may be exponential in the number of variables and constraints of the linear programming problem.
Recommendations
- Pivoting rules directing the simplex method through all feasible vertices of Klee-Minty examples
- Practical finite pivoting rules for the simplex method
- What is the worst case behavior of the simplex algorithm?
- New variants of finite criss-cross pivot algorithms for linear programming
- The criss-cross method can take (n^d) pivots
Cites work
- A convergent criss-cross method
- Efficient generation of the binary reflected gray code and its applications
- scientific article; zbMATH DE number 3466805 (Why is no real title available?)
- scientific article; zbMATH DE number 3626518 (Why is no real title available?)
- New Finite Pivoting Rules for the Simplex Method
- Some Simple Applications of the Travelling Salesman Problem
- The Criss-Cross Method for Solving Linear Programming Problems
- Worst case behavior of the steepest edge simplex method
Cited in
(18)- A new family of exponential LP problems
- Pivoting rules directing the simplex method through all feasible vertices of Klee-Minty examples
- Pivot rules for linear programming: A survey on recent theoretical developments
- An exterior point simplex algorithm for (general) linear programming problems
- On extremal behaviors of Murty's least index method
- Criss-cross methods: A fresh view on pivot algorithms
- Combinatorial redundancy detection
- An efficient simplex type algorithm for sparse and dense linear programs.
- Steepest-edge rule and its number of simplex iterations for a nondegenerate LP
- A linear programming instance with many crossover events
- The role of pivoting in proving some fundamental theorems of linear algebra
- Three nearly scaling-invariant versions of an exterior point algorithm for linear programming
- A new proof for the criss-cross method for quadratic programming
- scientific article; zbMATH DE number 1380759 (Why is no real title available?)
- Exterior point simplex-type algorithms for linear and network optimization problems
- The criss-cross method can take (n^d) pivots
- Exponential lower bounds for many pivot rules for the simplex method
- An efficient algorithm for vertex enumeration of arrangement
This page was built for publication: An exponential example for Terlaky's pivoting rule for the criss-cross simplex method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911455)
