DATA-LEVEL PARALLEL SOLUTION OF MIN-COST NETWORK FLOW PROBLEMS USING E-RELAXATIONS

doi:10.1016/0377-2217(94)90060-4

Return

DATA-LEVEL PARALLEL SOLUTION OF MIN-COST NETWORK FLOW PROBLEMS USING E-RELAXATIONS

1994-12-01

Xiaoye Li

Stavros A. Zenios

DOI：10.1016/0377-2217(94)90060-4

Original

Save

View PDF

Abstract

En 中文

We discuss the data-parallel implementation of the epsilon-relaxation algorithm for the solution of min-cost network flow problems. For transportation problems a Gauss-Seidel variant is implemented on the two-dimensional communication grid of a massively parallel Connection Machine CM-2. For arbitrary network topologies - i.e. transhipment problems - we implement a Jacobi algorithm using the hypercube communication network. A new parallel flow-calculation procedure increases the level of parallelism at every iteration of the algorithm and improves its performance. Extensive computational results are reported with network problems with up to 1 million arcs.

Keywords:

NETWORK OPTIMIZATION

PARALLEL COMPUTING

RELAXATION ALGORITHMS

GRAPHS

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.