Paper Info
Title
A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
Abstract
In this paper, we present a constant-factor approximation algorithm for the unsplittable flow problem on a path. This improves on the previous best known approximation factor of O(log n). The approximation ratio of our algorithm is 7+e for any e0. In the unsplittable flow problem on a path, we are given a capacitated path P and n tasks, each task having a demand, a profit, and start and end vertices. The goal is to compute a maximum profit set of tasks, such that for each edge e of P, the total demand of selected tasks that use e does not exceed the capacity of e. This is a well-studied problem that occurs naturally in various settings, and therefore it has been studied under alternative names, such as resource allocation, bandwidth allocation, resource constrained scheduling, temporal knapsack and interval packing. Polynomial time constant factor approximation algorithms for the problem were previously known only under the no-bottleneck assumption (in which the maximum task demand must be no greater than the minimum edge capacity). We introduce several novel algorithmic techniques, which might be of independent interest: a framework which reduces the problem to instances with a bounded range of capacities, and a new geometrically inspired dynamic program which solves a special case of the maximum weight independent set of rectangles problem to optimality. In addition, we show that the problem is strongly NP-hard even if all edge capacities are equal and all demands are either 1, 2, or 3.
Year
DOI
Venue
2011
10.1109/FOCS.2011.10
SIAM J. Comput.
Keywords
DocType
Volume
profitability,polynomial time,linear program,data structure
Conference
43
Issue
ISSN
Citations 
2
0272-5428
27
PageRank 
References 
Authors
0.96
15
3
Name
Order
Citations
PageRank
Paul Bonsma128720.46
Jens Schulz2744.85
Andreas Wiese325218.23