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

      0 references
      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
      [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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references