文章基本信息

标题：Approximation Algorithms for the Unsplittable Flow Problem on Paths and Trees
本地全文：下载
作者：Khaled Elbassioni ; Naveen Garg ; Divya Gupta 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2012
卷号：18
页码：267-275
DOI：10.4230/LIPIcs.FSTTCS.2012.267
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Approximation Algorithms; Integer Decomposition; Linear Programming; Scheduling; Unsplittable Flows