A quasi-PTAS for unsplittable flow on line graphs

ABSTRACT

We study the Unsplittable Flow Problem (UFP) on line graphs and cycles, focusing on the long-standing open question of whether the problem is APX-hard. We describe a deterministic quasi-polynomial time approximation scheme for UFP on line graphs, thereby ruling out an APX-hardness result, unless NP ⊆ DTIME(2^polylog(n)). Our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. We extend this result to undirected cycle graphs.Earlier results on this problem included a polynomial time (2+ε)-approximation under the assumption that no demand exceeds any edge capacity (the "no-bottleneck assumption") and a super-constant integrality gap if this assumption did not hold. Unlike most earlier work on UFP, our results do not require a no-bottleneck assumption.

REFERENCES

• 1: Susanne Albers , Sanjeev Arora , Sanjeev Khanna, Page replacement for general caching problems, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.31-40, January 17-19, 1999, Baltimore, Maryland, United States
• 2: 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]
• 3: 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]
• 4: 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
• 5: Amotz Bar-Noy , Reuven Bar-Yehuda , Ari Freund , Joseph Naor , Baruch Schieber, A unified approach to approximating resource allocation and scheduling, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.735-744, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335410]
• 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 , 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
• 9: 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
• 10: C. Chekuri, M. Mydlarz, and F. B. Shepherd. Multicommodity demand flow in a tree. In Proc. 30th International Colloquium on Automata, Languages and Programming, pages 410--425, 2003.
• 11: S. Fortune, J. E. Hopcroft, and J. Wylie. The directed subgraph homeomorphism problem. Theor. Comput. Sci., 10:111--121, 1980.
• 12: N. Garg, V. V. Vazirani, and M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3--20, 1997.
• 13: 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]
• 14: N. G. Hall and M. J. Magazine. Maximizing the value of a space mission. European Journal of Operational Research, 78:224--241, 1994.
• 15: R. M. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85--103. Plenum Press, New York, NY, 1972.
• 16: Jon Michael Kleinberg , Michel X. Goemans, Approximation algorithms for disjoint paths problems, 1996
• 17: Cynthia A. Phillips , R. N. Uma , Joel Wein, Off-line admission control for general scheduling problems, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.879-888, January 09-11, 2000, San Francisco, California, United States
• 18: Alexander Schrijver , Paul Seymour , Peter Winkler, The Ring Loading Problem, SIAM Journal on Discrete Mathematics, v.11 n.1, p.1-14, Feb. 1998 [doi>10.1137/S0895480195294994]
• 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 (FOCS '97), p.416, October 19-22, 1997

INDEX TERMS

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

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, approximation scheme, resource allocation, scheduling, unsplittable flow