A simplex variant solving an m × d linear program in O(min(m2, d2) expected number of pivot steps
- 1 December 1987
- journal article
- Published by Elsevier in Journal of Complexity
- Vol. 3 (4) , 372-387
- https://doi.org/10.1016/0885-064x(87)90007-0
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d OnlyMathematics of Operations Research, 1986
- Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithmMathematical Programming, 1986
- Random linear programs with many variables and few constraintsMathematical Programming, 1986
- A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimensionJournal of the ACM, 1985
- A new polynomial-time algorithm for linear programmingCombinatorica, 1984
- On the average number of steps of the simplex method of linear programmingMathematical Programming, 1983
- Random polytopes: Their definition, generation and aggregate propertiesMathematical Programming, 1982
- Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex MethodMathematics of Operations Research, 1982
- An experimental study of the simplex methodProceedings of Symposia in Applied Mathematics, 1963
- The computational algorithm for the parametric objective functionNaval Research Logistics Quarterly, 1955