A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths
A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths
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 …