The all-or-nothing flow problem in directed graphs with symmetric demand pairs

详细信息    查看全文

• 作者：Chandra Chekuri ; Alina Ene
• 关键词：68W25
• 刊名：Mathematical Programming
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：154
• 期：1-2
• 页码：249-272
• 全文大小：547 KB
• 参考文献：1.Adler, I.: Directed tree-width examples. J Comb. Theory Ser. B 97(5), 718鈥?25 (2007)MATH CrossRef
  2.Andrews, M., Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K., Zhang, L.: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica 30(5), 485鈥?20 (2010)MATH MathSciNet CrossRef
  3.Andrews, M., Chuzhoy, J., Khanna, S., Zhang, L.: Hardness of the undirected edge-disjoint paths problem with congestion. In: Proceeding of IEEE FOCS, pp. 226鈥?41 (2005)
  4.Chekuri, C., Chuzhoy, J.: Large-treewidth graph decompositions and applications. In: Proceedings of ACM STOC (2013)
  5.Chekuri, C., Chuzhoy, J.: Polynomial bounds for the grid-minor theorem. In: Proceedings of ACM STOC (2014)
  6.Chekuri, C., Ene, A.: Poly-logarithmic approximation for maximum node disjoint paths with constant congestion. In: Proceedings of ACM-SIAM SODA (2013)
  7.Chekuri, C., Kannan, S., Raja, A., Viswanath, P.: Multicommodity flows and cuts in polymatroidal networks. In: Proceedings of ITCS, pp. 399鈥?08 (2012)
  8.Chekuri, C., Khanna, S., Shepherd, F.B.: The all-or-nothing multicommodity flow problem. SIAM J. Comput. 42(4), 1467鈥?493 (2013)MATH MathSciNet CrossRef
  9.Chekuri, C., Khanna, S., Shepherd, F.B.: Multicommodity flow, well-linked terminals, and routing problems. In: Proceedings of ACM STOC, pp. 183鈥?92 (2005)
  10.Chekuri, C., Khanna, S., Shepherd, F.B.: Well-linked terminals for node-capacitated routing problems. Manuscript (2005)
  11.Chekuri, C., Khanna, S., Shepherd, F.B.: An \(O(\sqrt{n})\) approximation and integrality gap for disjoint paths and unsplittable flow. Theory Comput. 2(7), 137鈥?46 (2006)MathSciNet CrossRef
  12.Chekuri, C., Mydlarz, M., Shepherd, F.B.: Multicommodity demand flow in a tree and packing integer programs. ACM Trans. Algorithms 3(3), 27 (2007)MathSciNet CrossRef
  13.Chuzhoy, J.: Routing in undirected graphs with constant congestion. ArXiv preprint arXiv:鈥?107.鈥?554 (2011). Extended abstract in STOC 2012
  14.Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K.: Hardness of routing with congestion in directed graphs. In: Proceedings of ACM STOC, pp. 165鈥?78 (2007)
  15.Chuzhoy, J., Khanna, S.: Polynomial flow-cut gaps and hardness of directed cut problems. J. ACM 56(2), 6 (2009)MathSciNet CrossRef
  16.Chuzhoy, J., Li, S.: A polylogarithimic approximation algorithm for edge-disjoint paths with congestion 2. In: Proceedings of IEEE FOCS (2012)
  17.Even, S., Itai, A., Shamir, A.: On the complexity of timetable and multicommodity flow problems. SIAM J. Comput. 5(4), 691鈥?03 (1976)MATH MathSciNet CrossRef
  18.Feige, U., Hajiaghayi, M.T., Lee, J.R.: Improved approximation algorithms for minimum weight vertex separators. SIAM J. Comput. 38, 629鈥?57 (2008)MathSciNet CrossRef
  19.Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theor. Comput. Sci. 10(2), 111鈥?21 (1980)MATH MathSciNet CrossRef
  20.Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3鈥?0 (1997)MATH MathSciNet CrossRef
  21.Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. J. Comb. Theory Ser. B 82(1), 138鈥?54 (2001)MATH MathSciNet CrossRef
  22.Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85鈥?03. Plenum press, New York (1972)
  23.Kawarabayashi, K., Kreutzer, S.: An excluded grid theorem for digraphs with forbidden minors. In: Proceedings of ACM-SIAM SODA (2014)
  24.Kobayashi, Y., Kawarabayashi, K-I, Kreutzer, S.: An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem. In: Proceedings of ACM STOC (2014)
  25.Klein, P.N., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of ACM STOC, pp. 682鈥?90 (1993)
  26.Klein, P.N., Plotkin, S.A., Rao, S., Tardos, E.: Approximation algorithms for Steiner and directed multicuts. J. Algorithms 22(2), 241鈥?69 (1997)MATH MathSciNet CrossRef
  27.Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787鈥?32 (1999)MATH MathSciNet CrossRef
  28.Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica 15(2), 215鈥?45 (1995)MATH MathSciNet CrossRef
  29.Reed, B.: Introducing directed tree width. Electr. Notes Discr. Math. 3, 222鈥?29 (1999)CrossRef
  30.Saks, Michael E., Samorodnitsky, Alex, Zosin, Leonid: A lower bound on the integrality gap for minimum multicut in directed networks. Combinatorica 24(3), 525鈥?30 (2004)MATH MathSciNet CrossRef
  31.Srinivasan, A.: Improved approximations for edge-disjoint paths, unsplittable flow, and related routing problems. In: Proceedings of IEEE FOCS, pp. 416鈥?25 (1997)
  
• 作者单位：Chandra Chekuri (1)
  Alina Ene (2) (3)
  
  1. Department of Computer Science, University of Illinois at Urbana-Champaign, Chicago, IL, USA
  2. Center for Computational Intractability, Princeton University, Princeton, NJ, USA
  3. Department of Computer Science and DIMAP, University of Warwick, Coventry, UK
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

We study the approximability of the All-or-Nothing multicommodity flow problem in directed graphs with symmetric demand pairs (SymANF). The input consists of a directed graph \(G = (V, E)\) and a collection of (unordered) pairs of nodes \(\mathcal {M}= \left\{ s_1t_1, s_2t_2, \ldots , s_kt_k\right\} \). A subset \(\mathcal {M}'\) of the pairs is routable if there is a feasible multicommodity flow in \(G\) such that, for each pair \(s_it_i \in \mathcal {M}'\), the amount of flow from \(s_i\) to \(t_i\) is at least one and the amount of flow from \(t_i\) to \(s_i\) is at least one. The goal is to find a maximum cardinality subset of the given pairs that can be routed. Our main result is a poly-logarithmic approximation with constant congestion for SymANF. We obtain this result by extending the well-linked decomposition framework of Chekuri et al. (2005) to the directed graph setting with symmetric demand pairs. We point out the importance of studying routing problems in this setting and the relevance of our result to future work. Mathematics Subject Classification 68W25