A CONSTANT-FACTOR APPROXIMATION ALGORITHM FOR UNSPLITTABLE FLOW ON PATHS

作者：Bonsma Paul^*; Schulz Jens; Wiese Andreas

来源：SIAM Journal on Computing, 2014, 43(2): 767-799.

DOI：10.1137/120868360

• unsplittable flow
• resource allocation
• maximum weight independent set
• constantfactor approximation
• strong NP-hardness

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+ epsilon for any epsilon> 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 + epsilon)- 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.

• 出版日期2014