| Article ID: | iaor20133239 |
| Volume: | 39 |
| Issue: | 2 |
| Start Page Number: | 88 |
| End Page Number: | 91 |
| Publication Date: | Mar 2011 |
| Journal: | Operations Research Letters |
| Authors: | Mizuno Shinji, Kitahara Tomonari |
| Keywords: | error bound, simplex algorithm |
Kitahara and Mizuno (2010) 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.