An exponential example for Terlaky's pivoting rule for the criss-cross simplex method

DOI10.1007/BF01585729MaRDI QIDQ911455zbMATH OpenOpenAlexWikidataFDO

Authors N. E. Zubov

Publication date 1990

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01585729

zbMATH Keywords

Gray codecriss-cross simplex methodTerlaky's pivoting rule

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25)

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 \(\Omega(n^d)\) pivots

Cites work

• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3626518 (Why is no real title available?)
• A convergent criss-cross method
• Efficient generation of the binary reflected gray code and its applications
• 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

(14)

• Exterior point simplex-type algorithms for linear and network optimization problems
• Combinatorial redundancy detection
• On extremal behaviors of Murty's least index method
• Steepest-edge rule and its number of simplex iterations for a nondegenerate LP
• Criss-cross methods: A fresh view on pivot algorithms
• The role of pivoting in proving some fundamental theorems of linear algebra
• Pivot rules for linear programming: A survey on recent theoretical developments
• The criss-cross method can take \(\Omega(n^d)\) pivots
• Pivoting rules directing the simplex method through all feasible vertices of Klee-Minty examples
• An exterior point simplex algorithm for (general) linear programming problems
• A new family of exponential LP problems
• An efficient simplex type algorithm for sparse and dense linear programs.
• Three nearly scaling-invariant versions of an exterior point algorithm for linear programming
• A new proof for the criss-cross method for quadratic programming

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)