Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
From MaRDI portal
Publication:3755229
DOI10.1007/BF01580645zbMath0618.90061MaRDI QIDQ3755229
Publication date: 1986
Published in: Mathematical Programming (Search for Journal in Brave)
Related Items
A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps, Parametric linear programming and anti-cycling pivoting rules, A tree traversal algorithm for decision problems in knot theory and 3-manifold topology, A Friendly Smoothed Analysis of the Simplex Method, An algorithm for disjunctive programs, George Dantzig's impact on the theory of computation, New results on the average behavior of simplex algorithms, Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
- On the average number of steps of the simplex method of linear programming
- New results on the average behavior of simplex algorithms
- A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only
- Linear Programming in Linear Time When the Dimension Is Fixed
- The Average number of pivot steps required by the Simplex-Method is polynomial
- Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
- New Finite Pivoting Rules for the Simplex Method
- On the expected number of linear complementarity cones intersected by random and semi-random rays
- Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
- Bimatrix Equilibrium Points and Mathematical Programming
