Abstract | ||
---|---|---|
In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the dual simplex method with Dantzig’s rule for LP. The bound is comparable with the bound given by Kitahara and Mizuno (in press) [3] for the primal simplex method. We apply the result to the maximum flow problem and get a strong polynomial bound. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1016/j.orl.2012.01.004 | Operations Research Letters |
Keywords | Field | DocType |
Dual simplex method,Linear programming,Basic feasible solutions,Maximum flow problem | Combinatorics,Mathematical optimization,Simplex algorithm,Revised simplex method,Polynomial,Upper and lower bounds,Maximum flow problem,Linear programming,Mathematics | Journal |
Volume | Issue | ISSN |
40 | 3 | 0167-6377 |
Citations | PageRank | References |
3 | 0.48 | 2 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Tomonari Kitahara | 1 | 24 | 6.61 |
Shinji Mizuno | 2 | 792 | 153.37 |