(Almost) tight bounds and existence theorems for confluent flows

ABSTRACT

A flow is said to be confluent if at any node all the flow leaves along a single edge. Given a directed graph G with k sinks and non-negative demands on all the nodes of G, we consider the problem of determining a confluent flow that routes every node demand to some sink such that the maximum congestion at a sink is minimized. Confluent flows arise in a variety of application areas, most notably in networking; in fact, most flows in the Internet are confluent since Internet routing is destination based.We present near-tight approximation algorithms, hardness results, and existence theorems for confluent flows. The main result of this paper is a polynomial-time algorithm for determining a confluent flow with congestion at most 1 + ln(k) in G, if G admits a splittable flow with congestion at most 1. We complement this result in two directions. First, we present a graph G that admits a splittable flow with congestion at most 1, yet no confluent flow with congestion smaller than Hk, thus establishing tight upper and lower bounds to within an additive constant less than 1. Second, we show that it is NP-hard to approximate the congestion of an optimal confluent flow to within a factor of (lg k)/2, thus resolving the polynomial-time approximability to within a multiplicative constant. We also consider a demand maximization version of the problem. We show that if G admits a splittable flow of congestion at most 1, then a variant of the congestion minimization algorithm yields a confluent flow in G with congestion at most 1 that satisfies 1/3 fraction of total demand.We show that the gap between confluent flows and splittable flows is much smaller, if the underlying graph were k connected. In particular, we prove that k-connected graphs with k sinks admit confluent flows of congestion less than C + dmax, where C is the congestion of the best splittable flow, and dmax is the maximum demand of any node in G. The proof of this existence theorem is non-constructive and relies on topological techniques introduced in [16].

REFERENCES

• 1: Jiangzhuo Chen , Rajmohan Rajaraman , Ravi Sundaram, Meet and merge: approximation algorithms for confluent flows, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780598]
• 2: 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
• 3: Uriel Feige, A threshold of ln n for approximating set cover (preliminary version), Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.314-318, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237977]
• 4: L. Ford, Jr. and D. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399--404, 1956.
• 5: L. Ford, Jr. and D. Fulkerson. Flows in Networks. Princeton University Press, Princeton, NJ, 1962.
• 6: S. Fortune, J. Hopcroft, and J. Wyllie. The directed subgraph homeomorphism problem. Theoretical Computer Science, 10:111--121, 1980.
• 7: A. Frank. Combinatorial algorithms, algorithmic proofs. PhD thesis, Eötvös University, Budapest, 1976. In Hungarian.
• 8: 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]
• 9: Venkatesan Guruswami , Sanjeev Khanna , Rajmohan Rajaraman , Bruce Shepherd , Mihalis Yannakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Journal of Computer and System Sciences, v.67 n.3, p.473-496, November 2003 [doi>10.1016/S0022-0000(03)00066-7]
• 10: E. Györi. On division of graphs to connected subgraphs. In Proceedings of the Fifth Hungarian Combinatorial Colloquium, Budapest, 1976.
• 11: Samir Khuller , Balaji Raghavachari , Neal Young, Designing multi-commodity flow trees, Information Processing Letters, v.50 n.1, p.49-55, April 8, 1994 [doi>10.1016/0020-0190(94)90044-2]
• 12: J. M. Kleinberg, Single-source unsplittable flow, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.68, October 14-16, 1996
• 13: 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
• 14: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, Apr. 1990 [doi>10.1007/BF01585745]
• 15: Lorenz Dean H. , Orda Ariel , Raz Danny , Author:, How good can IP routing be?, Certer for Discrete Mathematics & Theoretical Computer Science, 2001
• 16: L. Lovász. A homology theory for spanning trees of a graph. Acta Mathematica Academiae Scientiarum Hungaricae, 30(3-4):241--251, 1977.
• 17: J. Wang and K. Nahrstedt. Hop-by-hop routing algorithms for premium-class traffic in diffserv networks. In Proceedings of IEEE INFOCOM, 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, network flow, routing, tight bounds