Efficient parallel algorithms for the minimum cost flow problem

DOI10.1023/A:1022613603828MaRDI QIDQ1379929zbMATH OpenOpenAlexWikidataFDO

Authors Patrizia Beraldi, Francesca Guerriero, Roberto Musmanno

Publication date 5 March 1998

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1023/a:1022613603828

zbMATH Keywords

parallel implementationsshared memory multiprocessors\(\varepsilon\)-relaxation algorithmsauction algorithmslinear minimum cost flow

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Recommendations

• Parallel algorithms for the assignment and minimum-cost flow problems
• Parallel algorithms for solving the convex minimum cost flow problem
• scientific article; zbMATH DE number 870979
• Parallel primal-dual methods for the minimum cost flow problem
• Parallel algorithms for the maximum flow problem with minimum lot sizes
• Sequential and parallel algorithms for minimum flows.
• scientific article; zbMATH DE number 1263274
• Efficient algorithms for minimum-cost flow problems with piecewise-linear convex costs
• A fast parallel algorithm for minimum-cost small integral flows

Cites work

• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 47262 (Why is no real title available?)
• scientific article; zbMATH DE number 51132 (Why is no real title available?)
• scientific article; zbMATH DE number 53116 (Why is no real title available?)
• scientific article; zbMATH DE number 724212 (Why is no real title available?)
• scientific article; zbMATH DE number 3231710 (Why is no real title available?)
• A Computation Study on Start Procedures, Basis Change Criteria, and Solution Algorithms for Transportation Problems
• An Auction Algorithm for Shortest Paths
• An auction algorithm for the max-flow problem
• Benefit-Cost Analysis of Coding Techniques for the Primal Transportation Algorithm
• Data-level parallel solution of min-cost network flow problems using \(\varepsilon\)-relaxations
• Efficient parallel algorithms for the minimum cost flow problem
• Finding Minimum-Cost Circulations by Successive Approximation
• Monotone networks
• NETGEN: A Program for Generating Large Scale Capacitated Assignment, Transportation, and Minimum Cost Flow Network Problems
• Parallel Simplex for Large Pure Network Problems: Computational Testing and Sources of Speedup
• Parallel primal-dual methods for the minimum cost flow problem
• Parallel shortest path auction algorithms
• Relaxation Methods for Minimum Cost Ordinary and Generalized Network Flow Problems
• Solution of large dense transportation problems using a parallel primal algorithm
• The auction algorithm: A distributed relaxation method for the assignment problem
• The network simplex method on a multiprocessor

Cited in

(11)

• More efficient parallel flow algorithms
• The parallel computation of minimum cost paths in graphs by stream contraction
• A parallel blocking flow algorithm for acyclic networks
• Dual coordinate step methods for linear network flow problems
• Sequential and parallel algorithms for minimum flows.
• Parallel algorithms for the assignment and minimum-cost flow problems
• Parallel algorithms for the maximum flow problem with minimum lot sizes
• Data-level parallel solution of min-cost network flow problems using \(\varepsilon\)-relaxations
• Parallel algorithms for solving the convex minimum cost flow problem
• Parallel shortest path auction algorithms
• Efficient parallel algorithms for the minimum cost flow problem

Describes a project that uses

Uses Software

• RELAX4
• NETGEN

This page was built for publication: Efficient parallel algorithms for the minimum cost flow problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1379929)