Improved bounds for the unsplittable flow problem

ABSTRACT

In this paper we consider the unsplittable flow problem (UFP): given a directed or undirected network G = (V, E) with edge capacities and a set of terminal pairs (or requests) with associated demands, find a subset of the pairs of maximum total demand for which a single flow path can be chosen for each pair so that for every edge, the sum of the demands of the paths crossing the edge does not exceed its capacity. We study the UFP both in the offline (all requests are given from the beginning) and the online (requests arrive at the system one after the other) setting. For this we introduce a new graph parameter, the flow number. With the help of the flow number we develop a general method for transforming arbitrary multicommodity flow solutions into solutions that use short paths only, generalizing a theorem of Leighton and Rao [17]. Both the parameter and the method may therefore be of independent interest. They allow us to prove upper bounds on the approximation ratio and competitive ratio of algorithms for the UFP that are significantly below all previous upper bounds.

REFERENCES

• 1: B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-competitive on-line routing. In Proc. of the 34th IEEE Symposium on Foundations of Computer Science, pages 32-40, 1993.
• 2: Yossi Azar , Oded Regev, Strongly Polynomial Algorithms for the Unsplittable Flow Problem, Proceedings of the 8th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.15-29, June 13-15, 2001
• 3: Alok Baveja , Aravind Srinivasan, Approximation Algorithms for Disjoint Paths and Related Routing and Packing Problems, Mathematics of Operations Research, v.25 n.2, p.255-280, May 2000 [doi>10.1287/moor.25.2.255.12228]
• 4: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 5: A. Chakrabarti, C. Chekuri, A. Gupta, and A. Kumar. Approximation algorithms for the unsplittable flow problem. Unpublished manuscript, 2001.
• 6: 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
• 7: Venkatesan Guruswami , Sanjeev Khanna , Rajmohan Rajaraman , Bruce Shepherd , Mihalis Yannakakis, Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.19-28, May 01-04, 1999, Atlanta, Georgia, United States [doi>10.1145/301250.301262]
• 8: Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, 1996
• 9: Jon M. Kleinberg, Decision algorithms for unsplittable flow and the half-disjoint paths problem, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.530-539, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276867]
• 10: J. Kleinberg , R. Rubinfeld, Short paths in expander graphs, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.86, October 14-16, 1996
• 11: J. Kzeinberg , E. Tardos, Disjoint paths in densely embedded graphs, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.52, October 23-25, 1995
• 12: Stavros G. Kolliopoulos , Clifford Stein, Improved Approximation Algorithms for Unsplittable Flow Problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.426, October 19-22, 1997
• 13: Stavros G. Kolliopoulos , Clifford Stein, Approximating Disjoint-Path Problems Using Greedy Algorithms and Packing Integer Programs, Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.153-168, June 22-24, 1998
• 14: Petr Kolman , Christian Scheideler, Simple on-line algorithms for the maximum disjoint paths problem, Proceedings of the thirteenth annual ACM symposium on Parallel algorithms and architectures, p.38-47, July 2001, Crete Island, Greece [doi>10.1145/378580.378586]
• 15: F. Thomson Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1991
• 16: T. Leighton and S. Rao. An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proc. of the 29th IEEE Symposium on Foundations of Computer Science, pages 422-431, 1988.
• 17: 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]
• 18: Michael Molloy , Bruce Reed, Further algorithmic aspects of the local lemma, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.524-529, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276866]
• 19: 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]
• 20: Christian Scheideler , J. Van Leeuwen , J. Hartmanis , G. Goos, Universal Routing Strategies for Interconnection Networks, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 21: C. Scheideler. Probabilistic Methods for Coordination Problems. Habilitation thesis, University of Paderborn, July 2000.
• 22: A. Srinivasan, Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.416, October 19-22, 1997