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.8665656447410583
0 references
0.8435280919075012
0 references
0.8435234427452087
0 references
0.8393966555595398
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