TY - JOUR

T1 - A constant-factor approximation algorithm for unsplittable flow on paths

AU - Bonsma, Paul

AU - Schulz, Jens

AU - Wiese, Andreas

PY - 2014

Y1 - 2014

N2 - 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 total demand of selected tasks that use e does not exceed the capacity of e. This is a well-studied problem that has been described under alternative names, such as resource allocation, bandwidth allocation, resource constrained scheduling, temporal knapsack, and interval packing. We present a polynomial time constant-factor approximation algorithm for this problem. This improves on the previous best known approximation ratio of O(log n). The approximation ratio of our algorithm is 7+ε for any ε < 0. 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 to optimality a special case of the problem of finding a maximum weight independent set of rectangles. In the setting of resource augmentation, wherein the capacities can be slightly violated, we give a (2 + ε)-approximation algorithm. In addition, we show that the problem is strongly NP-hard even if all edge capacities are equal and all demands are either 1, 2, or 3.

AB - 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 total demand of selected tasks that use e does not exceed the capacity of e. This is a well-studied problem that has been described under alternative names, such as resource allocation, bandwidth allocation, resource constrained scheduling, temporal knapsack, and interval packing. We present a polynomial time constant-factor approximation algorithm for this problem. This improves on the previous best known approximation ratio of O(log n). The approximation ratio of our algorithm is 7+ε for any ε < 0. 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 to optimality a special case of the problem of finding a maximum weight independent set of rectangles. In the setting of resource augmentation, wherein the capacities can be slightly violated, we give a (2 + ε)-approximation algorithm. In addition, we show that the problem is strongly NP-hard even if all edge capacities are equal and all demands are either 1, 2, or 3.

KW - Constantfactor approximation

KW - Maximum weight independent set

KW - Resource allocation

KW - Strong NP-hardness

KW - Unsplittable flow

UR - http://www.scopus.com/inward/record.url?scp=84899655535&partnerID=8YFLogxK

U2 - 10.1137/120868360

DO - 10.1137/120868360

M3 - Article

AN - SCOPUS:84899655535

SN - 0097-5397

VL - 43

SP - 767

EP - 799

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -