The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems
by F. Bruce Shepherd and Adrian R. Vetta
Theory of Computing, Volume 13(20), pp. 1-25, 2017
Bibliography with links to cited articles
[1] Matthew Andrews, Julia Chuzhoy, Venkatesan Guruswami, Sanjeev Khanna, Kunal Talwar, and Lisa Zhang: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica, 30(5):485–520, 2010. [doi:10.1007/s00493-010-2455-9]
[2] Matthew Andrews and Lisa Zhang: Logarithmic hardness of the undirected edge-disjoint paths problem. J. ACM, 53(5):745–761, 2006. Preliminary version in STOC’05. [doi:10.1145/1183907.1183910]
[3] Yossi Azar and Oded Regev: Combinatorial algorithms for the unsplittable flow problem. Algorithmica, 44(1):49–66, 2006. Preliminary version in IPCO’01. [doi:10.1007/s00453-005-1172-z]
[4] Alok Baveja and Aravind Srinivasan: Approximation algorithms for disjoint paths and related routing and packing problems. Math. Oper. Res., 25(2):255–280, 2000. [doi:10.1287/moor.25.2.255.12228]
[5] Paul S. Bonsma, Jens Schulz, and Andrea Wiese: A constant-factor approximation algorithm for unsplittable flow on paths. SIAM J. Computing, 43(2):767–799, 2014. Preliminary version in FOCS’11. [doi:10.1137/120868360, arXiv:1102.3643]
[6] Moses Charikar, Joseph S. Naor, and Baruch Schieber: Resource optimization in QoS multicast routing of real-time multimedia. IEEE/ACM Transactions on Networking, 12(2):340–348, 2004. Preliminary version in INFOCOM’00. [doi:10.1109/TNET.2004.826288]
[7] Chandra Chekuri, Alina Ene, and Nitish Korula: Unsplittable flow in paths and trees and column-restricted packing integer programs. In Proc. 12th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’09), pp. 42–55. Springer, 2009. [doi:10.1007/978-3-642-03685-9_4]
[8] Chandra Chekuri and Sanjeev Khanna: Edge-disjoint paths revisited. ACM Trans. Algorithms, 3(4), 2007. Preliminary version in SODA’03. [doi:10.1145/1290672.1290683]
[9] Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd: An O() approximation and integrality gap for disjoint paths and unsplittable flow. Theory of Computing, 2(7):137–146, 2006. [doi:10.4086/toc.2006.v002a007]
[10] Chandra Chekuri, Sanjeev Khanna, and F. Bruce Shepherd: Edge-disjoint paths in planar graphs with constant congestion. SIAM J. Computing, 39(1):281–301, 2009. Preliminary version in STOC’06. [doi:10.1137/060674442]
[11] Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, and Adrian R. Vetta: (Almost) Tight bounds and existence theorems for single-commodity confluent flows. J. ACM, 54(4):16, 2007. Preliminary version in STOC’04. [doi:10.1145/1255443.1255444]
[12] Jiangzhuo Chen, Rajmohan Rajaraman, and Ravi Sundaram: Meet and merge: Approximation algorithms for confluent flows. J. Comput. System Sci., 72(3):468–489, 2006. Preliminary version in STOC’03. [doi:10.1016/j.jcss.2005.09.009]
[13] Julia Chuzhoy: Routing in undirected graphs with constant congestion. SIAM J. Computing, 45(4):1490–1532, 2016. Preliminary version in STOC’12. [doi:10.1137/130910464, arXiv:1107.2554]
[14] Julia Chuzhoy, Anupam Gupta, Joseph S. Naor, and Amitabh Sinha: On the approximability of some network design problems. ACM Trans. Algorithms, 4(2):23:1–17, 2008. Preliminary version in SODA’05. [doi:10.1145/1361192.1361200]
[15] Julia Chuzhoy and Shi Li: A polylogarithmic approximation algorithm for edge-disjoint paths with congestion 2. J. ACM, 63(5):45:1–51, 2016. Preliminary version in FOCS’12. [doi:10.1145/2893472, arXiv:1208.1272]
[16] Steven Cosares and Iraj Saniee: An optimization problem related to balancing loads on SONET rings. Telecommunication Systems, 3(2):165–181, 1994. [doi:10.1007/BF02110141]
[17] Yefim Dinitz, Naveen Garg, and Michel X. Goemans: On the single-source unsplittable flow problem. Combinatorica, 19(1):17–41, 1999. Preliminary version in FOCS’98. [doi:10.1007/s004930050043]
[18] Patrick Donovan, F. Bruce Shepherd, Adrian R. Vetta, and Gordon Wilfong: Degree-constrained network flows. In Proc. 39th STOC, pp. 681–688. ACM Press, 2007. [doi:10.1145/1250790.1250889]
[19] Daniel Dressler and Martin Strehler: Capacitated confluent flows: complexity and algorithms. In Proc. 7th Internat. Conf. on Algorithms and Complexity (CIAC’10), pp. 347–358. Springer, 2010. [doi:10.1007/978-3-642-13073-1_31]
[20] Steven Fortune, John Hopcroft, and James Wyllie: The directed subgraph homeomorphism problem. Theor. Comput. Sci., 10(2):111–121, 1980. [doi:10.1016/0304-3975(80)90009-2]
[21] 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. System Sci., 67(3):473–496, 2003. Preliminary version in STOC’99. [doi:10.1016/S0022-0000(03)00066-7]
[22] Jon M. Kleinberg: Approximation Algorithms for Disjoint Paths Problems. Ph. D. thesis, MIT, 1996. Available from DSpace@MIT.
[23] Jon M. Kleinberg: Single-source unsplittable flow. In Proc. 37th FOCS, pp. 68–77. IEEE Comp. Soc. Press, 1996. [doi:10.1109/SFCS.1996.548465]
[24] Jon M. Kleinberg and Éva Tardos: Approximations for the disjoint paths problem in high-diameter planar networks. J. Comput. System Sci., 57(1):61–73, 1998. Preliminary version in STOC’95. [doi:10.1006/jcss.1998.1579]
[25] Stavros G. Kolliopoulos and Clifford Stein: Approximating disjoint-path problems using packing integer programs. Math. Program., 99(1):63–87, 2004. Preliminary version in IPCO’98. [doi:10.1007/s10107-002-0370-6]
[26] Petr Kolman: A note on the greedy algorithm for the unsplittable flow problem. Inform. Process. Lett., 88(3):101–105, 2003. [doi:10.1016/S0020-0190(03)00351-X]
[27] Guyslain Naves, Nicolas Sonnerat, and Adrian R. Vetta: Maximum flows on disjoint paths. In Proc. 13th Internat. Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX’10), pp. 326–337. Springer, 2010. [doi:10.1007/978-3-642-15369-3_25]
[28] Thành Nguyen: On the disjoint paths problem. Oper. Res. Lett., 35(1):10–16, 2007. [doi:10.1016/j.orl.2006.02.001]
[29] Neil Robertson and Paul D. Seymour: Graph minors. XIII. The disjoint paths problem. J. Comb. Theory, Ser. B, 63(1):65–110, 1995. [doi:10.1006/jctb.1995.1006]
[30] Loïc Seguin-Charbonneau and F. Bruce Shepherd: Maximum edge-disjoint paths in planar graphs with congestion 2. In Proc. 52nd FOCS, pp. 200–209. IEEE Comp. Soc. Press, 2011. [doi:10.1109/FOCS.2011.30]
[31] F. Bruce Shepherd: Single-sink multicommodity flow with side constraints. In Research Trends in Combinatorial Optimization, pp. 429–450. Springer, 2009. [doi:10.1007/978-3-540-76796-1_20]
[32] F. Bruce Shepherd, Adrian R. Vetta, and Gordon Wilfong: Polylogarithmic approximations for the capacitated single-sink confluent flow problem. In Proc. 56th FOCS, pp. 748–758. IEEE Comp. Soc. Press, 2015. [doi:10.1109/FOCS.2015.51]