guest ::
| Home > Articles > Published articles > A new strongly polynomial dual network simplex algorithm |
| Home > Articles > Published articles > A new strongly polynomial dual network simplex algorithm |
| Date: | 1997 |
| 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 log n) log n) time for the network with n nodes and m arcs. This complexity is better than the complexity of Orlin, Plotkin and Tardos' (1993) dual network simplex algorithm by a factor of m/n. . |
| Rights: | Tots els drets reservats.  |
| Language: | Anglès |
| Document: | Article ; recerca ; Versió publicada |
| Subject: | Dual simplex algorithm ; Minimum cost network flow problem ; Network simplex algorithm |
| Published in: | Mathematical Programming, vol. 78 n. 2 (1997) p. 131-148, ISSN 0025-5610 |
 UAB restricted access |
