The maximum concurrent flow problem

The maximum concurrent flow problem

0.00 Avg rating0 Votes
Article ID: iaor1995709
Country: United States
Volume: 37
Issue: 2
Start Page Number: 318
End Page Number: 334
Publication Date: Apr 1990
Journal: Journal of the Association for Computing Machinery
Authors: ,
Abstract:

The maximum concurrent flow problem (MCFP) is a multicommodity flow problem in which every pair of entities can send and receive flow concurrently. The ratio of the flow supplied between a pair of entities to the predefined demand for that pair is called throughput and must be the same for all pairs of entities for a concurrent flow. The MCFP objective is to maximize the throughput, subject to the capacity constraints. The authors develop a fully polynomial-time approximation scheme for the MCFP for the case of arbitrary demands and uniform capacity. Computational results are presented. It is shown that the problem of associating costs (distances) to the edges so as to maximize the minimum-cost of routing the concurrent flow is the dual of the MCFP. A path-cut type duality theorem to expose the combinatorial structure of the MCFP is also derived. The present duality theorems are proved constructively for arbitrary demands and uniform capacity using the algorithm. Applications include packet-switched networks, and cluster analysis.

Reviews

Required fields are marked *. Your email address will not be published.