(Almost) Tight bounds and existence theorems for single-commodity confluent flows

ABSTRACT

A flow of a commodity is said to be confluent if at any node all the flow of the commodity leaves along a single edge. In this article, we study single-commodity confluent flow problems, where we need to route given node demands to a single destination using a confluent flow. Single- and multi-commodity confluent flows arise in a variety of application areas, most notably in networking; in fact, most flows in the Internet are (multi-commodity) confluent flows since Internet routing is destination based.

We present near-tight approximation algorithms, hardness results, and existence theorems for minimizing congestion in single-commodity confluent flows. The maximum edge congestion of a single-commodity confluent flow occurs at one of the incoming edges of the destination. Therefore, finding a minimum-congestion confluent flow is equivalent to the following problem: given a directed graph G with k sinks and non-negative demands on all the nodes of G, determine a confluent flow that routes every node demand to some sink such that the maximum congestion at a sink is minimized.

The main result of this article 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 H_k, the kth harmonic number, 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 (log₂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 is k-connected. In particular, we prove that k-connected graphs with k sinks admit confluent flows of congestion less than C + d_max, where C is the congestion of the best splittable flow, and d_max is the maximum demand of any node in G. The proof of this existence theorem is non-constructive and relies on topological techniques introduced by Lovász.

REFERENCES

• 1: Bertsekas, D. 1999. Nonlinear Programming. Athena Scientific, Belmont, MA.
• 2: 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]
• 3: Dinitz, Y., Garg, N., and Goemans, M. 1999. On the single-source unsplittable flow problem. Combinatorica 19, 17--41.
• 4: Uriel Feige, A threshold of ln n for approximating set cover, Journal of the ACM (JACM), v.45 n.4, p.634-652, July 1998 [doi>10.1145/285055.285059]
• 5: Ford, Jr., L., and Fulkerson, D. 1956. Maximal flow through a network. Canad. J. Math. 8, 399--404.
• 6: Ford, Jr., L., and Fulkerson, D. 1962. Flows in Networks. Princeton University Press, Princeton, NJ.
• 7: Fortune, S., Hopcroft, J., and Wyllie, J. 1980. The directed subgraph homeomorphism problem. Theoret. Comput. Sci. 10, 111--121.
• 8: Frank, A. 1976. Combinatorial algorithms, algorithmic proofs. Ph.D. dissertation. Eötvös University, Budapest. In Hungarian.
• 9: G. Gallo , M. D. Grigoriadis , R. E. Tarjan, A fast parametric maximum flow algorithm and applications, SIAM Journal on Computing, v.18 n.1, p.30-55, Feb. 1989 [doi>10.1137/0218003]
• 10: 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]
• 11: 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]
• 12: Győri, E. 1976. On division of graphs to connected subgraphs. In Proceedings of the 5th Hungarian Combinatorial Colloquium. Budapest, Hungary.
• 13: Hatcher, A. 2002. Algebraic Topology. Cambridge University Press, Cambridge, UK.
• 14: 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]
• 15: J. M. Kleinberg, Single-source unsplittable flow, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.68, October 14-16, 1996
• 16: 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
• 17: 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, January 1990 [doi>10.1007/BF01585745]
• 18: Lorenz Dean H. , Orda Ariel , Raz Danny , Author:, How good can IP routing be?, Certer for Discrete Mathematics & Theoretical Computer Science, 2001
• 19: Lovász, L. 1977. A homology theory for spanning trees of a graph. Acta Mathematica Academiae Scientiarum Hungaricae 30, 3-4, 241--251.
• 20: Megiddo, N. 1977. A good algorithm for lexicographically optimal flows in multi-terminal networks. Bull. AMS 83, 3 (May), 407--409.
• 21: Jun Wang , Klara Nahrstedt, Hop-by-hop routing algorithms for premium traffic, ACM SIGCOMM Computer Communication Review, v.32 n.5, November 2002 [doi>10.1145/774749.774760]

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