No label defined (Q3677503)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3898607
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3898607 |
Statements
1985
0 references
survey
0 references
average complexity
0 references
simplex method
0 references
inequality constraints
0 references
stochastic model
0 references
sign invariance model
0 references
rotation symmetry model
0 references
0.8783975839614868
0 references
0.8730926513671875
0 references
0.8696582913398743
0 references
[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.
0 references