A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths

Paul Bonsma, Jens Schulz, Andreas Wiese

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 compu…