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

• 成果类型: Article
• 署名作者: Chekuri, Chandra; Ene, Alina
• 署名单位: University of Illinois System; University of Illinois Chicago; University of Illinois Chicago Hospital; Princeton University; University of Warwick; University of Warwick
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0856-z
• 发表日期: 2015
• 页码: 249-272
• 关键词: edge-disjoint paths; Approximation algorithms; tree-width; congestion; multicut

摘要

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 and a collection of (unordered) pairs of nodes . A subset of the pairs is routable if there is a feasible multicommodity flow in such that, for each pair , the amount of flow from to is at least one and the amount of flow from to 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.