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-5MaRDI QIDQ1974584zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

linear programminglower boundsimplex methodaverage-case complexity

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60)

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

Cited in

(10)

• Empirical Studies on the Average Efficiency of Simplex Variants under Rotation Symmetry
• scientific article; zbMATH DE number 1041033 (Why is no real title available?)
• The complex interior-boundary method for linear and nonlinear programming with linear constraints
• A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only
• A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
• A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
• A spectral approach to polytope diameter
• Hybrid-LP: finding advanced starting points for simplex, and pivoting LP methods
• The average number of pivot steps of the simplex-algorithm based on a generalized rotation-symmetry-model
• A steepest feasible direction method for linear programming. Derivation and embedding in the simplex method

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)