A polynomial dual simplex algorithm for the generalized circulation problem |
| |
| Authors: | Donald Goldfarb Zhiying Jin Yiqing Lin |
| |
| Affiliation: | (1) Department of Industrial Engineering and Operations Research, Columbia University, New York, New York 10027, US;(2) GTE Laboratories, 40 Sylvan Road, Waltham, MA 02154, US;(3) United Technologies Research Center, 411 Silver Lane, East Hartford, CT 06108, US |
| |
| Abstract: | This paper presents a polynomial-time dual simplex algorithm for the generalized circulation problem. An efficient implementation of this algorithm is given that has a worst-case running time of O(m 2(m+nlogn)logB), where n is the number of nodes, m is the number of arcs and B is the largest integer used to represent the rational gain factors and integral capacities in the network. This running time is as fast as the running time of any combinatorial algorithm that has been proposed thus far for solving the generalized circulation problem. Received: June 1998 / Accepted: June 27, 2001?Published online September 17, 2001 |
| |
| Keywords: | : network flows – generalized circulation – generalized maximum flow – dual simplex algorithm – arc excess – excess scaling |
| 本文献已被 SpringerLink 等数据库收录！ |
|
