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. |
Year | DOI | Venue |
---|---|---|
2011 | 10.1016/j.orl.2011.01.003 | Oper. Res. Lett. |
Keywords | Field | DocType |
simplex method,minimum value,linear programming,positive element,simple variant,different basic feasible solution,basic feasible solutions,klee–minty’s lp,upper bound,basic feasible solution,linear program | Mathematical optimization,Combinatorics,Simplex algorithm,Revised simplex method,Upper and lower bounds,Simple variant,Extreme value theory,Linear programming,Linear complementarity problem,Mathematics | Journal |
Volume | Issue | ISSN |
39 | 2 | Operations Research Letters |
Citations | PageRank | References |
3 | 0.74 | 1 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tomonari Kitahara | 1 | 24 | 6.61 |
Shinji Mizuno | 2 | 792 | 153.37 |