On strongly polynomial dual simplex algorithms for the maximum flow problem |
| |
Authors: | Donald Goldfarb Wei Chen |
| |
Institution: | (1) Department of Industrial Engineering and Operations Research, Columbia University, 10027 New York, NY, USA |
| |
Abstract: | Several pivot rules for the dual network simplex algorithm that enable it to solve a maximum flow problem on ann-node,m-arc network in at most 2nm pivots and O(n
2 m) time are presented. These rules are based on the concept of apreflow and depend upon the use of node labels which are either the lengths of a shortestpseudoaugmenting path from those nodes to the sink node orvalid underestimates of those lengths. Extended versions of our algorithms are shown to solve an important class of parametric
maximum flow problems with no increase in the worst-case pivot and time bounds of these algorithms.
This research was supported in part by NSF Grants DMS 91-06195, DMS 94-14438, and CDR 84-21402 and DOE Grant DE-FG02-92ER25126. |
| |
Keywords: | Dual simplex method Maximum flow Parametric maximum flow Preflow Pseudoaugmenting path Strongly polynomial Valid distance labels |
本文献已被 SpringerLink 等数据库收录! |
|