A primal simplex algorithm that solves the maximum flow problem in at mostnm pivots and O(n 2 m) time |
| |
Authors: | Donald Goldfarb Jianxiu Hao |
| |
Affiliation: | (1) Department of Industrial Engineering and Operations Research, Columbia University, 10027 New York, NY, USA;(2) GTE Laboratories, 02254 Waltham, MA, USA |
| |
Abstract: | We propose a primal network simplex algorithm for solving the maximum flow problem which chooses as the arc to enter the basis one that isclosest to the source node from amongst all possible candidates. We prove that this algorithm requires at mostnm pivots to solve a problem withn nodes andm arcs, and give implementations of it which run in O(n2m) time. Our algorithm is, as far as we know, the first strongly polynomial primal simplex algorithm for solving the maximum flow problem.This research was supported in part by NSF Grants DMS 85-12277 and CDR 84-21402 and ONR Contract N00014-87-K0214. |
| |
Keywords: | Simplex method maximum flow strongly polynomial network flow |
本文献已被 SpringerLink 等数据库收录! |
|