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.
[ .pdf ]
[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].

This file has been generated by bibtex2html 1.74