A logarithmic approximation for unsplittable flow on line graphs

ABSTRACT

We consider the unsplittable flow problem on a line. In this problem, we are given a set of n tasks, each specified by a start time s_i, an end time t_i, a demand d_i > 0, and a profit p_i > 0. A task, if accepted, requires d_i units of "bandwidth" from time s_i to t_i and accrues a profit of p_i. For every time t, we are also specified the available bandwidth c_t, and the goal is to find a subset of tasks with maximum profit subject to the bandwidth constraints.

In this paper, we present the first polynomial-time O(log n)-approximation algorithm for this problem. No polynomial-time o(n)-approximation was known prior to this work. Previous results for this problem were known only in more restrictive settings, in particular, either if the given instance satisfies the so-called "no-bottleneck" assumption: max_i d_i ≤ min_t c_t, or else if the ratio of the maximum to the minimum demands and ratio of the maximum to the minimum capacities are polynomially (or quasi-polynomially) bounded in n. Our result, on the other hand, does not require any of these assumptions.

Our algorithm is based on a combination of dynamic programming and rounding a natural linear programming relaxation for the problem. While there is an Ω(n) integrality gap known for this LP relaxation, our key idea is to exploit certain structural properties of the problem to show that instances that are bad for the LP can in fact be handled using dynamic programming.

REFERENCES

• 1: Matthew Andrews , Julia Chuzhoy , Lisa Zhang, Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.226-244, October 23-25, 2005 [doi>10.1109/SFCS.2005.41]
• 2: Matthew Andrews , Lisa Zhang, Hardness of the undirected edge-disjoint paths problem, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060632]
• 3: 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
• 4: Nikhil Bansal , Amit Chakrabarti , Amir Epstein , Baruch Schieber, A quasi-PTAS for unsplittable flow on line graphs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132617]
• 5: Amotz Bar-Noy , Reuven Bar-Yehuda , Ari Freund , Joseph (Seffi) Naor , Baruch Schieber, A unified approach to approximating resource allocation and scheduling, Journal of the ACM (JACM), v.48 n.5, p.1069-1090, September 2001 [doi>10.1145/502102.502107]
• 6: 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]
• 7: Gruia Calinescu , Amit Chakrabarti , Howard J. Karloff , Yuval Rabani, Improved Approximation Algorithms for Resource Allocation, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.401-414, May 27-29, 2002
• 8: Amit Chakrabarti , Chandra Chekuri , Anupam Gupta , Amit Kumar, Approximation Algorithms for the Unsplittable Flow Problem, Algorithmica, v.47 n.1, p.53-78, January 2007 [doi>10.1007/s00453-006-1210-5]
• 9: C. Chekuri, S. Khanna, and B. Shepherd, An O(√n) Approximation and Integrality Gap for Disjoint Paths and UFP, Theory of Computing, Vol 2, 137--146, 2006.
• 10: Chandra Chekuri , Marcelo Mydlarz , F. Bruce Shepherd, Multicommodity demand flow in a tree and packing integer programs, ACM Transactions on Algorithms (TALG), v.3 n.3, p.27-es, August 2007 [doi>10.1145/1273340.1273343]
• 11: S. Fortune, J. E. Hopcroft, and J. Wylie, The directed subgraph homeomorphism problem, Theor. Comput. Sci., 10:111--121, 1980.
• 12: Alan M. Frieze, Edge-Disjoint Paths in Expander Graphs, SIAM Journal on Computing, v.30 n.6, p.1790-1801, 2001 [doi>10.1137/S0097539700366103]
• 13: N. Garg, V. V. Vazirani, and M. Yannakakis, Primaldual approximation algorithms for integral flow and multicut in trees, Algorithmica, 18(1):3--20, 1997.
• 14: 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]
• 15: Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, Massachusetts Institute of Technology, 1996
• 16: 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
• 17: Petr Kolman , Christian Scheideler, Improved bounds for the unsplittable flow problem, Journal of Algorithms, v.61 n.1, p.20-44, September, 2006 [doi>10.1016/j.jalgor.2004.07.006]
• 18: A. Phillips, R. N. Uma and J. Wein, Off-line Admission Control for General Scheduling Problems, Journal of Scheduling, 3(6):365--381, 2000.
• 19: 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, p.416, October 19-22, 1997
• 20: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Dynamic programming