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

Chandra Chekuri, Alina Ene

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationInteger Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Proceedings
PublisherSpringer-Verlag Berlin Heidelberg
Pages222-233
Number of pages12
ISBN (Print)9783319075563
DOIs
StatePublished - 2014
Event17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014 - Bonn, Germany
Duration: Jun 23 2014Jun 25 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8494 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other17th International Conference on Integer Programming and Combinatorial Optimization, IPCO 2014
CountryGermany
CityBonn
Period6/23/146/25/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'The all-or-nothing flow problem in directed graphs with symmetric demand pairs'. Together they form a unique fingerprint.

Cite this