A new strongly polynomial dual network simplex algorithm
Armstrong, Ronald D.
Jin, Zhiying

Data: 1997
Resum: 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. .
Llengua: Anglès.
Document: Article ; recerca ; article ; publishedVersion
Matèria: Dual simplex algorithm ; Minimum cost network flow problem ; Network simplex algorithm
Publicat a: Mathematical Programming, vol. 78 n. 2 (1997) p. 131-148, ISSN 0025-5610

18 p, 973.6 KB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2017-10-28

   Favorit i Compartir