Elbassioni, Khaled ; Garg, Naveen ; Gupta, Divya ; Kumar, Amit ; Narula, Vishal ; Pal, Arindam (2012) Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees In: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012).
Full text not available from this repository.
Official URL: https://drops.dagstuhl.de/opus/volltexte/2012/3865
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.
| Item Type: | Conference or Workshop Item (Paper) |
|---|---|
| Source: | Copyright of this article belongs to Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. |
| ID Code: | 123523 |
| Deposited On: | 29 Sep 2021 11:34 |
| Last Modified: | 29 Sep 2021 11:34 |
Repository Staff Only: item control page
