Efficient Parallel Algorithms for the Minimum Cost Flow Problem

P. Beraldi, F. Guerriero and R. Musmanno
Additional contact information
P. Beraldi: Università della Calabria
F. Guerriero: Università della Calabria
R. Musmanno: Università della Calabria

Journal of Optimization Theory and Applications, 1997, vol. 95, issue 3, No 2, 530 pages

Abstract: Abstract In this paper, we propose efficient parallel implementations of the auction/sequential shortest path and the ∈-relaxation algorithms for solving the linear minimum cost flow problem. In the parallel auction algorithm, several augmenting paths can be found simultaneously, each of them starting from a different node with positive surplus. Convergence results of an asynchronous version of the algorithm are also given. For the ∈-relaxation method, there exist already parallel versions implemented on CM-5 and CM-2; our implementation is the first on a shared memory multiprocessor. We have obtained significant speedup values for the algorithms considered; it turns out that our implementations are effective and efficient.

Keywords: Network optimization; minimum cost flow problems; auction algorithms; parallel asynchronous algorithms; shared memory multiprocessors (search for similar items in EconPapers)
Date: 1997
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1022613603828 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:joptap:v:95:y:1997:i:3:d:10.1023_a:1022613603828

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1022613603828

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().