Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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

Tools
- Tools
+ Tools

Chekuri, Chandra and Ene, Alina (2014) The all-or-nothing flow problem in directed graphs with symmetric demand pairs. Mathematical Programming Series B . doi:10.1007/978-3-319-07557-0-19

[img]
Preview
PDF
WRAP_Ene_dir-anf-journal (2).pdf - Accepted Version - Requires a PDF viewer.

Download (635Kb) | Preview
Official URL: http://dx.doi.org/10.1007/s10107-014-0856-z

Request Changes to record.

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,...,sk tk }. A subset M of the pairs is routable if there is a feasible multicommodity flow in G such that, for each pair si ti ∈ M, the amount of flow from si to ti is at least one and the amount of flow from ti to si 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.

Item Type: Journal Article
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Computer Science
Library of Congress Subject Headings (LCSH): Directed graphs
Journal or Publication Title: Mathematical Programming Series B
Publisher: Springer
ISSN: 0025-5610
Official Date: 21 December 2014
Dates:
DateEvent
21 December 2014Published
10 December 2014Accepted
30 April 2014Submitted
DOI: 10.1007/978-3-319-07557-0-19
Status: Peer Reviewed
Publication Status: Published
Access rights to Published version: Restricted or Subscription Access
Funder: National Science Foundation (U.S.) (NSF), Toyota Technological Institute at Chicago (TTI)
Grant number: CCF-1016684 (NSF), CCF-1319376 (NSF), CCF-0844872 (NSF)
Version or Related Resource: Chekuri, C. and Ene, A. (2014). The all-or-nothing flow problem in directed graphs with symmetric demand pairs. In: Lee, J. and Vygen, J., (eds.) Integer Programming and Combinatorial Optimization : 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014 : proceedings. Lecture notes in computer science, 8494. Springer International Publishing, pp. 222-233.
Embodied As: 1
Related URLs:
  • Related item in WRAP

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us