TY - JOUR
T1 - The all-or-nothing flow problem in directed graphs with symmetric demand pairs
AU - Chekuri, Chandra
AU - Ene, Alina
N1 - Publisher Copyright:
© 2014, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.
PY - 2015/12/1
Y1 - 2015/12/1
N2 - 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 (Formula presented.) and a collection of (unordered) pairs of nodes (Formula presented.). A subset(Formula presented.) of the pairs is routable if there is a feasible multicommodity flow in $$G$$G such that, for each pair (Formula presented.), the amount of flow from (Formula presented.) is at least one and the amount of flow from (Formula presented.) 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.
AB - 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 (Formula presented.) and a collection of (unordered) pairs of nodes (Formula presented.). A subset(Formula presented.) of the pairs is routable if there is a feasible multicommodity flow in $$G$$G such that, for each pair (Formula presented.), the amount of flow from (Formula presented.) is at least one and the amount of flow from (Formula presented.) 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.
KW - 68W25
UR - http://www.scopus.com/inward/record.url?scp=84946407619&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84946407619&partnerID=8YFLogxK
U2 - 10.1007/s10107-014-0856-z
DO - 10.1007/s10107-014-0856-z
M3 - Article
AN - SCOPUS:84946407619
SN - 0025-5610
VL - 154
SP - 249
EP - 272
JO - Mathematical Programming
JF - Mathematical Programming
IS - 1-2
ER -