| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142736 | Operations Research Letters | 2011 | 4 Pages |
Abstract
Kitahara and Mizuno (2010)Â [2] get two upper bounds for the number of different basic feasible solutions generated by Dantzig's simplex method. The size of the bounds highly depends on the ratio between the maximum and the minimum values of all the positive elements of basic feasible solutions. We show that the ratio for a simple variant of Klee-Minty's LP is equal to the number of iterations by Dantzig's simplex method for solving it.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Tomonari Kitahara, Shinji Mizuno,