LIPIcs.FSTTCS.2012.267.pdf
- Filesize: 394 kB
- 9 pages
Document
Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees
Authors
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2012-12-14
Cite AsGet BibTex
Khaled Elbassioni, Naveen Garg, Divya Gupta, Amit Kumar, Vishal Narula, and Arindam Pal. 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). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 267-275, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
https://doi.org/10.4230/LIPIcs.FSTTCS.2012.267
https://doi.org/10.4230/LIPIcs.FSTTCS.2012.267
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.
Keywords
- Approximation Algorithms
- Integer Decomposition
- Linear Programming
- Scheduling
- Unsplittable Flows
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads