Please help transcribe this video using our simple transcription tool. You need to be logged in to do so.


In this paper, we present the first constant-factor approximation algorithm for the unsplittable flow problem on a path. This represents a large improvement over the previous best polynomial time approximation algorithm for this problem in its full generality, which was an $O(\log n)$-approximation algorithm; it also answers an open question by Bansal et~al.[SODA'09]. The approximation ratio of our algorithm is $7+\epsilon$ for any $\epsilon>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 the total demand of the selected tasks does not exceed the capacity of any edge on $P$. 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 and temporal knapsack. Poly nomial 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. We also give the first proof that the problem is strongly NP-hard; we show that this is true even if all edge capacities are equal and all demands are either 1, 2, or 3.

Questions and Answers

You need to be logged in to be able to post here.