A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths

In this paper, we present a constant-factor approximation algorithm for the unsplittable flow problem on a path. This improves on the previous best known approximation factor of O(log n). The approximation ratio of our algorithm is 7+e for any e>; 0. 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 occurs naturally in various settings, and therefore it has been studied under alternative names, such as resource allocation, bandwidth allocation, resource constrained scheduling, temporal knapsack and interval packing. Polynomial time constant factor approximation algorithms for the problem were previously known only under the no-bottleneck assumption (in which the maximum task demand must be no greater than the minimum edge capacity). 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 a special case of the maximum weight independent set of rectangles problem to optimality. 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.

Authors

• Paul S. Bonsma
• Jens Schulz
• Andreas Wiese

Keywords

• Approximation algorithms
• Approximation methods
• Polynomials
• Partitioning algorithms
• Heuristic algorithms
• Resource management
• Algorithm design and analysis
• Estimation Algorithm
• Constant Approximation
• Constant-factor Approximation Algorithm
• Unsplittable Flow
• Independent Set
• Dynamic Programming
• Algorithm For Problem
• Profit Maximization
• Flow Problem
• Minimum Capacity
• Algorithmic Techniques
• Bandwidth Allocation
• Strongly NP-hard
• General Case
• Linear Programming
• End Time
• Feasible Solution
• Approximate Solution
• Line Segment
• Polynomial-time Algorithm
• Representative Algorithms
• Small Tasks
• Linear Programming Relaxation
• Short Task
• Resource Allocation Problem
• Linear Programming Techniques
• Hardness Results
• Horizontal Segment
• resource allocation
• maximum weight independent set
• constant factor approximation
• strong NP-hardness