The all-or-nothing multicommodity flow problem

ABSTRACT

We consider the all-or-nothing multicommodity flow problem in general graphs. We are given a capacitated undirected graph G=(V,E,u) and set of k pairs s1 t1, s2t2, …, sktk. Each pair has a unit demand. The objective is to find a largest subset S of 1,2,…,k such that for every i in S we can send a flow of one unit between si and ti. Note that this differs from the edge-disjoint path problem (EDP) in that we do not insist on integral flows for the pairs. This problem is NP-hard, and APX-hard, even on trees. For trees, a 2--approximation is known for the cardinality case and a 4--approximation for the weighted case. In this paper we build on a recent result of Räcke on low congestion oblivious routing in undirected graphs to obtain a poly-logarithmic approximation for the all-or-nothing problem in general undirected graphs. The best previous known approximation for all-or-nothing flow problem was O(min(n<^2/3, √m)), the same as that for EDP. Our algorithm extends to the case where each pair siti has a demand dⁱ associated with it and we need to completely route dⁱ to get credit for pair i. We also consider the online admission control version where pairs arrive online and the algorithm has to decide immediately on its arrival whether to accept it or not. We obtain a randomized algorithm with a competitive ratio that is similar to the approximation ratio for the offline algorithm.

REFERENCES

• 1: David Applegate , Edith Cohen, Making intra-domain routing robust to changing and uncertain traffic demands: understanding fundamental tradeoffs, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863991]
• 2: James Aspnes , Yossi Azar , Amos Fiat , Serge Plotkin , Orli Waarts, On-line routing of virtual circuits with applications to load balancing and machine scheduling, Journal of the ACM (JACM), v.44 n.3, p.486-504, May 1997 [doi>10.1145/258128.258201]
• 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: B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-competitive online routing. Proc. of FOCS, 32--40, 1993.
• 5: 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
• 6: Yossi Azar , Edith Cohen , Amos Fiat , Haim Kaplan , Harald Racke, Optimal oblivious routing in polynomial time, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780599]
• 7: Nikhil Bansal , Avrim Blum , Shuchi Chawla , Adam Meyerson, Online oblivious routing, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777420]
• 8: Marcin Bienkowski , Miroslaw Korzeniowski , Harald Räcke, A practical algorithm for constructing oblivious routing schemes, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777418]
• 9: Amit Chakrabarti , Chandra Chekuri , Anuptam Gupta , Amit Kumar, Approximation Algorithms for the Unsplittable Flow Problem, Proceedings of the 5th International Workshop on Approximation Algorithms for Combinatorial Optimization, p.51-66, September 17-21, 2002
• 10: Chandra Chekuri , Sanjeev Khanna, On multi-dimensional packing problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.185-194, January 17-19, 1999, Baltimore, Maryland, United States
• 11: Chandra Chekuri , Sanjeev Khanna, Edge disjoint paths revisited, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 12: C. Chekuri, M. Mydlarz and F. B. Shepherd. Multicommodity Demand Flow in a Tree. Proc. of ICALP, 2003.
• 13: Julia Chuzhoy , Joseph (Seffi) Naor, New hardness results for congestion minimization and machine scheduling, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007364]
• 14: 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
• 15: S. Even, A. Itai and A. Shamir. On the complexity of timetable and multicommodity flow problems. SIAM J. on Computing, Vol 5, 691--703, 1976.
• 16: A. Frank. Packing paths, cuts, and circuits - a survey. In B. Korte, L. Lovász, H. J. Prömel, and A. Schrijver, eds., Paths, Flows and VLSI-Layout, 49--100. Springer Verlag, Berlin, 1990.
• 17: Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover, Proceedings of the 20th International Colloquium on Automata, Languages and Programming, p.64-75, July 05-09, 1993
• 18: 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]
• 19: Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777419]
• 20: J. M. Kleinberg, Single-source unsplittable flow, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.68, October 14-16, 1996
• 21: Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, 1996
• 22: 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
• 23: Petr Kolman , Christian Scheideler, Improved bounds for the unsplittable flow problem, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.184-193, January 06-08, 2002, San Francisco, California
• 24: Petr Kolman, A note on the greedy algorithm for the unsplittable flow problem, Information Processing Letters, v.88 n.3, p.101-105, 15 November 2003 [doi>10.1016/S0020-0190(03)00351-X]
• 25: 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]
• 26: Tom Leighton , Satish Rao , Aravind Srinivasan, Multicommodity Flow and Circuit Switching, Proceedings of the Thirty-First Annual Hawaii International Conference on System Sciences-Volume 7, p.459, January 06-09, 1998 [doi>10.1109/HICSS.1998.649241]
• 27: N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995. Preliminary version in Proc. of FOCS, 1994.
• 28: L. Lovász. Combinatorial Problems and Exercises. North-Holland, 1993.
• 29: B. Maggs, G. Miller, O. Parekh, R. Ravi, and S. L. M. Wu. Solving symmetric diagonally-dominant systems by preconditioning. Manuscript, 2002.
• 30: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 31: S. Plotkin. Competitive Routing of Virtual Circuits in ATM Networks. Survey in IEEE Journal on Selected Areas in Communications, 13(6):1128-1136, 1995.
• 32: 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]
• 33: Satish Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the fifteenth annual symposium on Computational geometry, p.300-306, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304983]
• 34: N. Robertson and P. D. Seymour. Outline of a disjoint paths algorithm. In B. Korte, L. Lovász, H. J. Prömel, and A. Schrijver, Eds., Paths, Flows and VLSI-Layout. Springer-Verlag, Berlin, 1990.
• 35: 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
• 36: Kasturi Varadarajan , Ganesh Venkataraman, Graph decomposition and a greedy algorithm for edge-disjoint paths, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana

INDEX TERMS

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

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

General Terms:
Algorithms, Theory

Keywords:
all-or-nothing multicommodity flow, approximation algorithms, edge disjoint paths, multicommodity flow, oblivious routing, online algorithms