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-5zbMath0949.90059OpenAlexW385102008MaRDI QIDQ1974584

Petra Huhn, Karl Heinz Borgwardt

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

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

Related Items (2)

Hybrid-LP: finding advanced starting points for simplex, and pivoting LP methods ⋮ The complex interior-boundary method for linear and nonlinear programming with linear constraints

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