On dual minimum cost flow algorithms

Jens Vygen

Mathematical Methods of Operations Research, 2002, vol. 56, issue 1, 126 pages

Abstract: We describe a new dual algorithm for the minimum cost flow problem. It can be regarded as a variation of the best known strongly polynomial minimum cost flow algorithm, due to Orlin. Indeed we obtain the same running time of O(m log m(m+n log n)), where n and m denote the number of vertices and the number of edges. However, in contrast to Orlin's algorithm we work directly with the capacitated network (rather than transforming it to a transshipment problem). Thus our algorithm is applicable to more general problems (like submodular flow) and is likely to be more efficient in practice. Our algorithm can be interpreted as a cut cancelling algorithm, improving the best known strongly polynomial bound for this important class of algorithms by a factor of m. On the other hand, our algorithm can be considered as a variant of the dual network simplex algorithm. Although dual network simplex algorithms are reportedly quite efficient in practice, the best worst-case running time known so far exceeds the running time of our algorithm by a factor of n. Copyright Springer-Verlag Berlin Heidelberg 2002

Keywords: Key words: Minimum cost flow problem; strongly polynomial algorithm; dual algorithms; cut cancelling; dual network simplex (search for similar items in EconPapers)
Date: 2002
References: Add references at CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://hdl.handle.net/10.1007/s001860200202 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:56:y:2002:i:1:p:101-126

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s001860200202

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().