A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps (Q1100853)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps |
scientific article; zbMATH DE number 4045040
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps |
scientific article; zbMATH DE number 4045040 |
Statements
A simplex variant solving an m\(\times d\) linear program in O(min(m 2,d 2)) expected number of pivot steps (English)
0 references
1987
0 references
The authors consider a linear program with m inequality constraints and d variables. Assuming a fairly general probabilistic distribution of the problem data they obtain the result that a variant of a simplex method, the parametric constraint-by-constraint algorithm, requires on the average at most 2(min(m,d)1) 2 pivots to solve the problem.
0 references
expected number of pivot steps
0 references
complexity
0 references
simplex method
0 references
parametric constraint-by-constraint algorithm
0 references
0 references
0 references
