No label defined (Q3346084)

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 3880432
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3880432

      Statements

      1983
      0 references
      average speed of the simplex method
      0 references
      self-dual parametric variation of the simplex method
      0 references
      0 references
      [For the entire collection see Zbl 0533.00035.] The author gives an exposition of his work on the average speed of the simplex method [see Math. Program. 27, 241-262 (1983; Zbl 0526.90060)]. Given the linear programming problem: (1) minimize cx, subject to Ax\(\geq b\), \(x\geq 0\), A is an \(m\times n\) matrix, x, \(c\in {\mathbb{R}}^ n\), \(b\in {\mathbb{R}}^ m\) and given a probability measure on the space \({\mathbb{R}}^{mn}\times {\mathbb{R}}^ m\times {\mathbb{R}}^ n\) of data (A,b,c) that satisfies three appropriately defined conditions, continuity, independence, symmetry, he denotes by \(\rho\) (m,n) the average number of iterations required to solve (1) by Dantzig's algorithm known as the self-dual parametric variation of the simplex method. He states and sketches the main theorem: let m be fixed and \(\epsilon\geq 0\) be given. Then, there exists a constant k depending on m and \(\epsilon\) such that \(\rho (m,n)\leq kn^{\epsilon}\).
      0 references

      Identifiers