DocumentCode :
2722499
Title :
A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths
Author :
Bonsma, Paul ; Schulz, Jens ; Wiese, Andreas
Author_Institution :
Comput. Sci. Dept., Humboldt Univ. zu Berlin, Berlin, Germany
fYear :
2011
fDate :
22-25 Oct. 2011
Firstpage :
47
Lastpage :
56
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 e>;0. 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.
Keywords :
approximation theory; computational complexity; dynamic programming; NP-hard; O(log n); constant factor approximation algorithm; maximum weight independent set; resource allocation; unsplittable flow problem; Algorithm design and analysis; Approximation algorithms; Approximation methods; Heuristic algorithms; Partitioning algorithms; Polynomials; Resource management; constant factor approximation; maximum weight independent set; resource allocation; strong NP-hardness; unsplittable flow;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on
Conference_Location :
Palm Springs, CA
ISSN :
0272-5428
Print_ISBN :
978-1-4577-1843-4
Type :
conf
DOI :
10.1109/FOCS.2011.10
Filename :
6108149
Link To Document :
بازگشت