Computer Science – Data Structures and Algorithms
Scientific paper
2011-02-17
Computer Science
Data Structures and Algorithms
37 pages, 5 figures Version 2 contains the same results as version 1, but the presentation has been greatly revised and improv
Scientific paper
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 has been studied under alternative names, such as resource allocation, bandwidth allocation, resource constrained scheduling, temporal knapsack and interval packing. We present a polynomial time constant-factor approximation algorithm for this problem. This improves on the previous best known approximation ratio of $O(\log n)$. The approximation ratio of our algorithm is $7+\epsilon$ for any $\epsilon>0$. 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 the setting of resource augmentation, wherein the capacities can be slightly violated, we give a $(2+\epsilon)$-approximation algorithm. 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.
Bonsma Paul
Schulz Jens
Wiese Andreas
No associations
LandOfFree
A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-380951