Meet and merge: approximation algorithms for confluent flows

ABSTRACT

In this paper we investigate the problem ofdetermining confluent flows with minimum congestion. A flow of a given commodity is said to be confluent if at any node all the flow of the commodity departs along a single edge. Confluent flows appear in a variety of application areas ranging from wireless communications to evacuations; in fact, most flows in the Internet are confluent since Internet routing is destination based.We consider the single commodity confluent flow problem, in which we are given an n-node directed network G, a sink t and supplies at each node, and the goal is to find a confluent flow that routes all the supplies to the sink while minimizing the maximum edge congestion. Our main result is an approximation algorithm, based on randomized rounding, for the special case when all the supplies are uniform; the algorithm finds a confluent flow with edge congestion O(C² log³ n) where C is the node congestion of an optimal splittable flow. This implies an Õ(√n) approximation algorithm for the problem. Our result relies on the analysis of a natural probabilistic process defined on directed acyclic graphs, that may be of independent interest.For tree networks, we present an optimal polynomial-time algorithm for a multi-sink generalization of the above confluent flow problem. We show that it is NP-hard to approximate the congestion of the optimal confluent flow for general networks to within a factor of 4/3. We also establish a lower bound on the gap between confluent and splittable flows, and consider multicommodity and fractional versions of confluent flow problems.

REFERENCES

• 1: N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, New York, NY, 1991.
• 2: K. Athreya and A. Vidyashankar. Branching processes. Technical Report TR--99--16, Department of Statistics, University of Georgia, 1999.
• 3: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 4: J. Chen, R. Rajaraman, and R. Sundaram. Meet and merge: Approximation algorithms for confluent flows. Technical report, College of Computer & Information Science, Northeastern University, March 2003.
• 5: Yefim Dinitz , Naveen Garg , Michel Goemans, On the Single-Source Unsplittable Flow Problem, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.290, November 08-11, 1998
• 6: W. Evans, C. Kenyon, Y. Peres, and L. Schulman. Broadcasting on trees and the ising model. Annals of Applied Probability, 10:410--433, 2000.
• 7: W. Feller. An Introduction to Probability Theory and its Applications, volume 1. Wiley, New York, NY, 1967.
• 8: L. Ford, Jr. and D. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399--404, 1956.
• 9: L. Ford, Jr. and D. Fulkerson. Flows in Networks. Princeton University Press, Princeton, NJ, 1962.
• 10: S. Fortune, J. Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10:111--121, 1980.
• 11: Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the Steiner group tree problem, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.253-259, January 25-27, 1998, San Francisco, California, United States
• 12: Anupam Gupta , Jon Kleinberg , Amit Kumar , Rajeev Rastogi , Bulent Yener, Provisioning a virtual private network: a network design problem for multicommodity flow, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.389-398, July 2001, Hersonissos, Greece [doi>10.1145/380752.380830]
• 13: Richard M. Karp , Yanjun Zhang, Bounded branching process and AND/OR tree evaluation, Random Structures & Algorithms, v.7 n.2, p.97-116, September 1995 [doi>10.1002/rsa.3240070202]
• 14: Samir Khuller , Balaji Raghavachari , Neal E. Young, Designing Multi-Commodity Flow Trees, Proceedings of the Third Workshop on Algorithms and Data Structures, p.433-441, August 11-13, 1993
• 15: Jon Kleinberg , Eva Tardos , Yuval Rabani, Fairness in Routing and Load Balancing, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.568, October 17-18, 1999
• 16: J. M. Kleinberg, Single-source unsplittable flow, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.68, October 14-16, 1996
• 17: Goran Konjevod , R. Ravi , Aravind Srinivasan, Approximation algorithms for the covering Steiner problem, Random Structures & Algorithms, v.20 n.3, p.465-482, May 2002 [doi>10.1002/rsa.10038]
• 18: Amit Kumar , Rajeev Rastogi , Avi Silberschatz , Bulent Yener, Algorithms for provisioning virtual private networks in the hose model, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.135-146, August 2001, San Diego, California, United States
• 19: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 20: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15:215--245, 1995.
• 21: Lorenz Dean H. , Orda Ariel , Raz Danny , Author:, How good can IP routing be?, Certer for Discrete Mathematics & Theoretical Computer Science, 2001
• 22: Madhav V. Marathe , R. Ravi , Ravi Sundaram , S. S. Ravi , Daniel J. Rosenkrantz , Harry B. Hunt, III, Bicriteria network design problems, Journal of Algorithms, v.28 n.1, p.142-171, July 1, 1998 [doi>10.1006/jagm.1998.0930]
• 23: C. McDiarmid. On the method of bounded differences. In J. Siemons, editor, Surveys in Combinatorics, pages 148--188. Cambridge University Press, Cambridge, UK, 1989.
• 24: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 25: Prabhakar Raghavan , Clark D. Tompson, Randomized rounding: a technique for provably good algorithms and algorithmic proofs, Combinatorica, v.7 n.4, p.365-374, Dec, 1987 [doi>10.1007/BF02579324]
• 26: Jeanette P. Schmidt , Alan Siegel , Aravind Srinivasan, Chernoff-Hoeffding Bounds for Applications with Limited Independence, SIAM Journal on Discrete Mathematics, v.8 n.2, p.223-250, May 1995 [doi>10.1137/S089548019223872X]
• 27: J. Wang and K. Nahrstedt. Hop-by-hop routing algorithms for premium-class traffic in diffserv networks. In Proc. of IEEE INFOCOM 2002, New York, NY, June 2002.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, confluent flow, multicommodity flow, network flow, randomization, rounding, routing