### The maximum concurrent flow problemThe maximum concurrent flow problem

Access Restriction
Subscribed

 Author Shahrokhi, Farhad ♦ Matula, D. W. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1990 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science 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 $\textit{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. We 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. Our duality theorems are proved constructively for arbitrary demands and uniform capacity using the algorithm. Applications include packet-switched networks [1, 4, 8], and cluster analysis [16]. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1990-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 37 Issue Number 2 Page Count 17 Starting Page 318 Ending Page 334

#### Open content in new tab

Source: ACM Digital Library