License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2012.267
URN: urn:nbn:de:0030-drops-38650
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3865/
Go to the corresponding LIPIcs Volume Portal

Elbassioni, Khaled ; Garg, Naveen ; Gupta, Divya ; Kumar, Amit ; Narula, Vishal ; Pal, Arindam

Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees

pdf-format:
26.pdf (0.4 MB)

Abstract

We study the Unsplittable Flow Problem (UFP) and related variants, namely UFP with Bag Constraints and UFP with Rounds, on paths and trees. We provide improved constant factor approximation algorithms for all these problems under the no bottleneck assumption (NBA), which says that the maximum demand for any source-sink pair is at most the minimum capacity of any edge. We obtain these improved
results by expressing a feasible solution to a natural LP relaxation of the UFP as a near-convex combination of feasible integral solutions.

BibTeX - Entry

@InProceedings{elbassioni_et_al:LIPIcs:2012:3865,
  author =	{Khaled Elbassioni and Naveen Garg and Divya Gupta and Amit Kumar and Vishal Narula and Arindam Pal},
  title =	{{Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
  pages =	{267--275},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2012/3865},
  URN =		{urn:nbn:de:0030-drops-38650},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.267},
  annote =	{Keywords: Approximation Algorithms, Integer Decomposition, Linear Programming, Scheduling, Unsplittable Flows}
}

Keywords: Approximation Algorithms, Integer Decomposition, Linear Programming, Scheduling, Unsplittable Flows
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Issue Date: 2012
Date of publication: 14.12.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI