The maximum concurrent flow problem

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. 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].

REFERENCES

• 1: ATTAR, R. A Distributive Adaptive Multi-path RoutingwConsistent and Conflicting Decision Making, '80/'81, Aiken Computation Laboratory, Harvard Univ., Cambridge, Mass.
• 2: Jr,R. P. Bianchini , J. P. Shen, Interprocessing traffic scheduling algorithm for multiple-processor networks, IEEE Transactions on Computers, v.36 n.4, p.396-409, April 1987 [doi>10.1109/TC.1987.1676922]
• 3: Jit Biswas , David W. Matula, Two flow routing algorithms for the maximum concurrent flow problem, Proceedings of 1986 ACM Fall joint computer conference, p.629-636, November 1986, Dallas, Texas, United States
• 4: BOORSTYN, R. R., AND FRANK, H. Large-scale network topological optimization. IEEE Communications (Jan. 1977), 29-47.
• 5: DIAZ, H., AND GHELLINK, G. Multicommodity maximum flow in planar networks (D-algorithm approach). CORE Discussion Paper No. 7212. Center for Operations Research and Econometrics, Louvain-la-Neuve, Belgium, 1972.
• 6: FORD, L. R., AND FULKERSON, D. R. A suggested computation for maximal multicommodity network flows. Manage. Sci. 5 (1958), 97-101.
• 7: FORD, L. R., AND FULKERSON, D.R. Flows in Networks. Princeton University Press, Princeton, N.J., 1962.
• 8: GERLA, M. A cut saturation algorithm for topological design of packet-switched communication networks. In Proceedings of the National Telecommunication Conference. Dec. 1974, pp. 1074-1085.
• 9: HARARY, F. Graph Theory. Addison-Wesley, Reading, Mass., 1969.
• 10: Hu, T.C. Integer Programming and Network Flows. Addison-Wesley, Reading, Mass., 1969.
• 11: IRI, M. On an extension of the maximum-flow minimum-cut theorem to multicommodity flows. J. Oper. Res. Soc. Japan 5, 4 (Dec. 1967), 691-703.
• 12: N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
• 13: Jeff L. Kennington , Richard V. Helgason, Algorithms for Network Programming, John Wiley & Sons, Inc., New York, NY, 1980
• 14: Kazuhiko Matsumoto , Takao Nishizeki , Nobuji Saito, Planar multicommodity flows, maximum matchings and negative cycles, SIAM Journal on Computing, v.15 n.2, p.495-510, May 1986 [doi>10.1137/0215034]
• 15: D. W. Matula, Concurrent flow and concurrent connectivity on graphs, Graph theory with applications to algorithms and computer science, John Wiley & Sons, Inc., New York, NY, 1985
• 16: MATULA, D.W. Divisive vs. agglomerative average linkage hierarchical clustering. In Classification as a Tool of Research. Gaul, W., and Schader, M., eds. North-Holland, Amsterdam, 1986, pp. 289-301.
• 17: OKAMURA, H., AND SEMOUR, P.D. Multicommodity flows in planar graphs. J. Comput. Theory, Ser. B 31 (1981), 75-81.
• 18: ONAGA, K. A multicommodity flow theorem. Trans. IECE, Japan, 53-.4, 7 (1970), 350-356.
• 19: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 20: PATTY, B.W. The basis suppression method for linear programs with special structure excluded by an objective side column. Ph.D. dissertation, Dept. of Operations Research and Engineering Management. Southern Methodist Univ., Dallas, Tex., 1984.
• 21: SHAHROKHI, F. Approximation algorithms for the maximum concurrent flow problem. ORSA J. Comput. 1, 2 (1989), 62-69.
• 22: Farhad Shahrokhi , David W. Matula, On solving large maximum concurrent flow problems, Proceedings of the 15th annual conference on Computer Science, p.205-209, February 1987, St. Louis, Missouri, United States [doi>10.1145/322917.322949]
• 23: TANG, D.T. Bi-path networks and multicommodity flows. IEEE Trans. Circuit Theory CT-I 1 (1964), 468-474.
• 24: Eva Tardos, A strongly polynomial algorithm to solve combinatorial linear programs, Operations Research, v.34 n.2, p.250-256, March-April 1986 [doi>10.1287/opre.34.2.250]
• 25: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 26: THOMPSON, B., AND MATULA, D.W. A flow rerouting algorithm for the maximum concurrent flow problem with variable capacities and demands, and its applications to cluster analysis. Tech. Rep. 86-CSE-12. Dept. of Computer Science and Engineering. Southern Methodist Univ., 1986.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout; Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Experimentation, Theory