Unsplittable Flow on a Short Path

Ilan Doron-Arad, Fabrizio Grandoni, Ariel Kulik

In the Unsplittable Flow on a Path problem UFP, we are given a path graph with edge capacities and a collection of tasks. Each task is characterized by a demand, a profit, and a su…