scientific article; zbMATH DE number 3898607
average complexityinequality constraintsrotation symmetry modelsign invariance modelsimplex methodstochastic modelsurvey
Random convex sets and integral geometry (aspects of convex geometry) (52A22) Geometric probability and stochastic geometry (60D05) Numerical mathematical programming methods (65K05) Analysis of algorithms and problem complexity (68Q25) Algorithms in computer science (68W99) Linear programming (90C05)
[For the entire collection see Zbl 0553.00015.] The author gives a survey over results on the average complexity of the simplex method. Especially, he deals with the average number of pivot steps which are required for the solution of a linear programming problem with m inequality constraints in n variables, where \(m\geq n.\) The average case analysis is motivated by the tremendous gap between the worst case complexity of this algorithm and practical experience. Whereas Klee, Minty and others could construct families of problems where the number of steps s increases exponentially with the dimension of the problem, the simplex method has turned out to be a very efficient and successful tool for solving usually occuring linear programs. An average case analysis of that algorithm requires three decisions in advance: which type of problems, which variant and which stochastic model for the distribution of problems shall be used. Almost all researchers in this field have analyzed parametric variants, but the stochastic models differ tremendously. The author discusses the so-called sign invariance model and reports on the main result under that model. After that he describes his own stochastic model (rotation symmetry model) and explains how his analysis did work. He concludes with a list of his main results (polynomiality, asymptotic bounds under special assumptions, generalizations) and with some open problems.
- scientific article; zbMATH DE number 4197740
- The simplex method. A probabilistic analysis
- The average computing time of the simplex method in a generalized rotational symmetry model
- How fast does the simplex method usually work? Or: the search for (stochastic) independence
- A simplex algorithm whose average number of steps is bounded between two quadratic functions of the smaller dimension
- Intelligent gradient search in linear programming
- The simplex method. A probabilistic analysis
- How fast does the simplex method usually work? Or: the search for (stochastic) independence
- scientific article; zbMATH DE number 3843665 (Why is no real title available?)
- scientific article; zbMATH DE number 3845338 (Why is no real title available?)
- Ein effektives simplexverfahren mit teiltableauwahl
- Improved asymptotic analysis of the average number of steps performed by the self-dual simplex algorithm
- An asymptotic estimate of the average number of steps of the parametric simplex method
- scientific article; zbMATH DE number 4027159 (Why is no real title available?)
- Empirical Studies on the Average Efficiency of Simplex Variants under Rotation Symmetry
- scientific article; zbMATH DE number 1041033 (Why is no real title available?)
- The average number of pivot steps of the simplex-algorithm based on a generalized rotation-symmetry-model
- A Sharp Upper Bound for the Expected Number of Shadow Vertices in LP-Polyhedra Under Orthogonal Projection on Two-Dimensional Planes
- scientific article; zbMATH DE number 3894829 (Why is no real title available?)
- The average computing time of the simplex method in a generalized rotational symmetry model
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3677503)