|
|||||
|
|
A new strongly polynomial dual network simplex algorithm |
|
| Authors: | Ronald D Armstrong Zhiying Jin |
| Institution: | (1) Present address: Department of Industrial Engineering and Operations Research, Columbia University, 10027 New York, NY, USA;(2) Graduate School of Management and RUTCOR — Rutgers Center for Operations Research, Rutgers University, 07102 Newark, NJ, USA |
| Abstract: | This paper presents a new dual network simplex algorithm for the minimum cost network flow problem. The algorithm works directly on the original capacitated network and runs in O(mn(m +n logn) logn) time for the network withn nodes andm arcs. This complexity is better than the complexity of Orlin, Plotkin and Tardos’ (1993) dual network simplex algorithm by a factor ofm/n. |
| Keywords: | Dual simplex algorithm Minimum cost network flow problem Network simplex algorithm |
| 本文献已被 SpringerLink 等数据库收录！ | |