A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only

DOI10.1287/moor.11.4.570zbMath0618.90064OpenAlexW2102721320MaRDI QIDQ3755232

Ilan Adler, Ron Shamir, Richard M. Karp

Publication date: 1986

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/moor.11.4.570

zbMATH Keywords

probabilistic modelspivoting ruleSimplex methodConstraint-By-Constraint procedure

Mathematics Subject Classification ID

Linear programming (90C05)

Related Items

A computationally stable solution algorithm for linear programs, A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps, Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm, Constraint optimal selection techniques (COSTs) for nonnegative linear programming problems, A primal-dual simplex method for linear programs, Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial, Selected bibliography on degeneracy