TY - GEN

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

AU - Chekuri, Chandra

AU - Ene, Alina

PY - 2014

Y1 - 2014

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 G = (V, E) and a collection of (unordered) pairs of nodes M = {s1t1,s2t2, S ktk}. A subset M′ of the pairs is routable if there is a feasible multicommodity flow in G such that, for each pair S iti ε 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 [6] 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 G = (V, E) and a collection of (unordered) pairs of nodes M = {s1t1,s2t2, S ktk}. A subset M′ of the pairs is routable if there is a feasible multicommodity flow in G such that, for each pair S iti ε 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 [6] 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.

UR - http://www.scopus.com/inward/record.url?scp=84958522647&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84958522647&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-07557-0_19

DO - 10.1007/978-3-319-07557-0_19

M3 - Conference contribution

AN - SCOPUS:84958522647

SN - 9783319075563

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 222

EP - 233

BT - Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Proceedings

PB - Springer-Verlag Berlin Heidelberg

T2 - 17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014

Y2 - 23 June 2014 through 25 June 2014

ER -