Some Distribution-Independent Results About the Asymptotic Order of the Average Number of Pivot Steps of the Simplex Method

Karl-Heinz Borgwardt

Type: Article

Publication Date: 1982-08-01

Citations: 124

DOI: https://doi.org/10.1287/moor.7.3.441

View Publication

Locations

Mathematics of Operations Research - View

Similar Works

Action	Title	Year	Authors
+	Empirical Studies on the Average Efficiency of Simplex Variants under Rotation Symmetry	1993	Karl Heinz Borgwardt Renate Damm Rudolf Donig Gabriele Joas
+	An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm	1996	Karl -Heinz K�fer
+	On the complexity of a pivot step of the revised simplex algorithm	1985	Victor Y. Pan
+ PDF Chat	On the Variance of the Number of Pivot Steps Required by the Simplex Algorithm	1994	Karl‐Heinz Küfer
+	A Note on the Distribution of the Number of Simplex Iterations to Optimality	2008	Sam Sup Kim Jennifer Switkes
+	On the number of pivots of Dantzig's simplex methods for linear and convex quadratic programs	2024	Shaoning Han Xinyao Zhang Jong‐Shi Pang
+	Subexponential lower bounds for randomized pivoting rules for the simplex algorithm	2011	Oliver Friedmann Thomas Dueholm Hansen Uri Zwick
+	The Efficiency of the Simplex Method: A Survey	1987	Ron Shamir
+	On the average number of steps of the simplex method of linear programming	1983	Steve Smale
+	Practical finite pivoting rules for the simplex method	1990	Ping Pan
+	The Average number of pivot steps required by the Simplex-Method is polynomial	1982	Karl Heinz Borgwardt
+	A note on the Edmonds-Fukuda pivoting rule for simplex algorithms	1987	Jens Clausen
+	Towards a Unified Framework for Randomized Pivoting Algorithms in Linear Programming	1999	Lukas Finschi K. Fukuda Hans-Jakob Lüthi
+ PDF Chat	Probabilistic Analysis of the Simplex Method	1988	Karl Heinx Borgwardt
+ PDF Chat	A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes	1999	Karl Heinz Borgwardt
+	A note on best pivot simplex method	2003	Tang Hui
+ PDF Chat	Average complexity of a gift-wrapping algorithm for determining the convex hull of randomly given points	1997	Karl Heinz Borgwardt
+	A largest-distance pivot rule for the simplex algorithm	2007	Ping-Qi PAN
+	Pivot vector method and its applications	1992	A. D. Tuniev
+ PDF Chat	Ideas Leading to a Better Bound on the Average Number of Pivot Steps for Solving an LP	1998	Karl Heinz Borgwardt

Works That Cite This (73)

Action	Title	Year	Authors
+ PDF Chat	Geometry of the Gass-Saaty parametric cost LP algorithm	1990	Victor Klee Peter Kleinschmidt
+ PDF Chat	Community Structures of Networks	2008	William Y. C. Chen Andreas Dress Winking Q. Yu
+	Conditioning of Random Conic Systems Under a General Family of Input Distributions	2008	Raphael Hauser Tobias Müller
+	The Efficiency of the Simplex Method: A Survey	1987	Ron Shamir
+	Mathematical Programming the State of the Art: Bonn 1982	1983	Achim Bachem Martin Grötschel Bernhard Körte
+	Decomposition Method	2013	Ping-Qi PAN
+ PDF Chat	Ideas Leading to a Better Bound on the Average Number of Pivot Steps for Solving an LP	1998	Karl Heinz Borgwardt
+	Pivotal Interior-Point Method	2013	Ping-Qi PAN
+ PDF Chat	Probabilistic Analysis of the Simplex Method	1988	Karl Heinx Borgwardt
+	Two-dimensional Second-Order Cone Programming	2009	Yu Xia

Works Cited by This (9)

Action	Title	Year	Authors
+	HOW GOOD IS THE SIMPLEX ALGORITHM	1970	Victor Klee George J. Minty
+ PDF Chat	�ber die konvexe H�lle von n zuf�llig gew�hlten Punkten	1963	A. R�nyi Robert A. Sulanke
+ PDF Chat	Die konvexe H�lle von n rotationssymmetrisch verteilten Punkten	1970	H. Carnal
+	The Probability that a Random Polytope is Bounded	1977	Brian K. Schmidt T. H. Mattheiss
+	Sur L'enveloppe convexe des nuages de points aleatoires dans <i>R<sup>n</sup></i>. I	1970	Henri-François Raynaud
+ PDF Chat	Some results in probabilistic geometry	1968	Wolfgang M. Schmidt
+	The simplex algorithm with the pivot rule of maximizing criterion improvement	1973	R. G. Jeroslow
+	The convex hull of a random set of points	1965	B. Efron
+	A class of linear programming problems requiring a large number of iterations	1965	Victor Klee