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

[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(√ --
  n) 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]