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.570zbMATH Open0618.90064OpenAlexW2102721320MaRDI QIDQ3755232FDOQ3755232

Authors: Ilan Adler, Ron Shamir, Richard 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

Recommendations

• A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps
• A lower bound on the average number of pivot-steps for solving linear programs. Valid for all variants of the simplex-algorithm
• 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
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• Solving Piecewise-Linear Programs: Experiments with a Simplex Approach
• A double-pivot simplex algorithm and its upper bounds of the iteration numbers

zbMATH Keywords

probabilistic modelspivoting ruleSimplex methodConstraint-By-Constraint procedure

Mathematics Subject Classification ID

Linear programming (90C05)

Cited In (10)

• Title not available (Why is that?)
• Constraint optimal selection techniques (COSTs) for nonnegative linear programming problems
• A lower bound on the average number of pivot-steps for solving linear programs. Valid for all variants of the simplex-algorithm
• Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial
• Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
• Selected bibliography on degeneracy
• Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems
• A primal-dual simplex method 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
• A computationally stable solution algorithm for linear programs

This page was built for publication: A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3755232)