Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method
From MaRDI portal
Publication:3964318
DOI10.1287/moor.7.3.441zbMath0498.90054OpenAlexW2049947556MaRDI QIDQ3964318
Publication date: 1982
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/moor.7.3.441
Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05) Linear programming (90C05)
Related Items
Random linear programs with many variables and few constraints ⋮ Unnamed Item ⋮ An external reconstruction approach (ERA) to linear programming ⋮ A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps ⋮ On Estimating Optimal Bases for Linear Programs ⋮ On the number of iterations of local improvement algorithms ⋮ Models of opinion control for agents in social networks ⋮ Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm ⋮ Karmarkar's projective method for linear programming: a computational survey ⋮ Foundations of operations research: from linear programming to data envelopment analysis ⋮ Strong polynomiality of the Gass-Saaty shadow-vertex pivoting rule for controlled random walks ⋮ Exterior point simplex-type algorithms for linear and network optimization problems ⋮ A computational study of redundancy in randomly generated polytopes ⋮ New results on the average behavior of simplex algorithms ⋮ On the asymptotic average number of efficient vertices in multiple objective linear programming ⋮ Low order polynomial bounds on the expected performance of local improvement algorithms ⋮ Fast finite methods for a system of linear inequalities ⋮ Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems ⋮ ON THE MONOTONICITY OF THE MOMENTS OF VOLUMES OF RANDOM SIMPLICES ⋮ Conditioning of random conic systems under a general family of input distributions ⋮ The expected number of extreme points of a random linear program ⋮ Geometry of the Gass-Saaty parametric cost LP algorithm ⋮ Computing in combinatorial optimization ⋮ ON THE MONOTONICITY OF THE EXPECTED VOLUME OF A RANDOM SIMPLEX ⋮ Moser's shadow problem ⋮ Recent trends in combinatorial optimization ⋮ A new efficient primal dual simplex algorithm
