A lower bound on the average number of pivot-steps for solving linear programs. Valid for all variants of the simplex-algorithm
DOI10.1007/S186-1999-8373-5zbMATH Open0949.90059OpenAlexW385102008MaRDI QIDQ1974584FDOQ1974584
Authors: K. H. Borgwardt, Petra Huhn 
Publication date: 7 May 2000
Published in: Mathematical Methods of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s186-1999-8373-5
Recommendations
- A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
- A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only
- On the variance of the number of pivot steps required by the simplex algorithm
- scientific article; zbMATH DE number 949658
- On the complexity of a pivot step of the revised simplex algorithm
- Subexponential lower bounds for randomized pivoting rules for the simplex algorithm
- A lower bound on the number of iterations of long-step primal-dual linear programming algorithms
- scientific article; zbMATH DE number 554743
Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60)
Cited In (10)
- Hybrid-LP: finding advanced starting points for simplex, and pivoting LP methods
- Title not available (Why is that?)
- Empirical Studies on the Average Efficiency of Simplex Variants under Rotation Symmetry
- A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
- A spectral approach to polytope diameter
- The average number of pivot steps of the simplex-algorithm based on a generalized rotation-symmetry-model
- A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only
- A steepest feasible direction method for linear programming. Derivation and embedding in the simplex method
- The complex interior-boundary method for linear and nonlinear programming with linear constraints
- A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
This page was built for publication: A lower bound on the average number of pivot-steps for solving linear programs. Valid for all variants of the simplex-algorithm
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1974584)
