A 2 + ε Approximation Algorithm for Unsplittable Flow on a Path

characterized by a subpath, a demand, and a profit. The goal is to find the most profitable subset of tasks whose total demand does not violate the edge capacities. This problem naturally arises in many settings such as bandwidth allocation, resource constrained scheduling, and interval packing.

We present a polynomial time 2+eps approximation algorithm for the problem. Key to this result is a complex geometrically inspired
dynamic program. Here each task is represented as a segment underneath
the capacity curve, and we identify a proper maze-like structure so that each passage of the maze is crossed by only O(1) tasks in the computed solution. This improves the previous best 7+eps approximation [Bonsma et al., FOCS 2011]. We remark that our improved approximation factor matches the best known approximation ratio for the considerably easier special case of uniform edge capacities.