An O(√n) Approximation and Integrality Gap for Disjoint Paths and Unsplittable Flow

by Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd

Theory of Computing, Volume 2(7), pp. 137-146, 2006

Bibliography with links to cited articles

[1]   Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, and Lisa Zhang: Hardness of the undirected edge-disjoint paths problem with congestion. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 226–244, 2005. [FOCS:10.1109/SFCS.2005.41].

[2]   Yossi Azar and Oded Regev: Combinatorial algorithms for the unsplittable flow problem. Algorithmica, 44(1):49–66, 2006. Preliminary version in Proc. of IPCO, 2001. [Algorithmica:yl21u55g402h8033, IPCO:eq2xun7jtdm8udue].

[3]   Alok Baveja and Aravind Srinivasan: Approximation algorithms for disjoint paths and related routing and packing problems. Math. Oper. Res., 25(2):255–280, 2000.

[4]   Chandra Chekuri and Sanjeev Khanna: Edge disjoint paths revisited. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 628–637, 2003. [SODA:644108.644212].

[5]   Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd: The all-or-nothing multicommodity flow problem. In Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), pp. 156–165, 2004. [STOC:1007352.1007383].

[6]   Chandra Chekuri, Marcelo Mydlarz, and F. Bruce Shepherd: Multicommodity demand flow in a tree. In Proceedings of 30th International Colloquium on Automata, Languages and Programming (ICALP), volume 2719 of Lecture Notes in Computer Science, pp. 410–425. Springer, 2003. [ICALP:du648d9x5721adll].

[7]   András Frank: Packing paths, cuts, and circuits - a survey. In B. Korte, L. Lovász, H. J. Prömel, and A. Schrijver, editors, Paths, Flows and VLSI-Layout, pp. 49–100. Springer Verlag, 1990.

[8]   Naveen Garg, Vijay V. Vazirani, and Mihalis Yannakakis: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica, 18(1):3–20, 1997. [Algorithmica:x1dykd3030ggac4w].

[9]   Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, and Mihalis Yannakakis: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems. J. Comput. Syst. Sci., 67(3):473–496, 2003. Preliminary version in Proc. of ACM STOC, 1999. [JCSS:10.1016/S0022-0000(03)00066-7, STOC:301250.301262].

[10]   Jon Kleinberg: Approximation algorithms for disjoint paths problems. PhD thesis, MIT, Cambridge, MA, May 1996.

[11]   Stavros Kolliopoulos: Edge disjoint paths and unsplittable flow. In Teofilo F. Gonzalez, editor, Handbook on Approximation Algorithms and Metaheuristics, CRC Computer and Information Science. Chapman and Hall, 2006. To appear.

[12]   Stavros G. Kolliopoulos and Clifford Stein: Approximating disjoint-path problems using packing integer programs. Math. Program., 99(1):63–87, 2004. Preliminary version in Proc. of IPCO, 1998. [MathProg:lh5yrd3peyp3kb3h, IPCO:upy56mcmrvfqdm84].

[13]   Petr Kolman: A note on the greedy algorithm for the unsplittable flow problem. Inf. Process. Lett., 88(3):101–105, 2003. [IPL:10.1016/S0020-0190(03)00351-X].

[14]   Petr Kolman and Christian Scheideler: Improved bounds for the unsplittable flow problem. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), pp. 184–193, 2002. [SODA:545381.545404].

[15]   Bin Ma and Lusheng Wang: On the inapproximability of disjoint paths and minimum steiner forest with bandwidth constraints. J. Comput. Syst. Sci., 60(1):1–12, 2000. [JCSS:10.1006/jcss.1999.1661].

[16]   Thanh Nguyen: On disjoint paths. Personal communication, August 2005.

[17]   Alexander Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. Springer-Verlag, Berlin Hiedelberg, 2003.

[18]    Kasturi R. Varadarajan and Ganesh Venkataraman: Graph decomposition and a greedy algorithm for edge-disjoint paths. In Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), pp. 379–380, 2004. [SODA:982792.982846].