New Approximation Schemes for Unsplittable Flow on a Path

Abstract

We study the unsplittable flow on a path problem which has received a lot of attention in the research community recently. Given is a path with capacities on its edges and a set of tasks where each task is characterized by a source and a sink vertex, a demand, and a profit. The goal is to find a subset of the tasks of maximum total profit such that all task demands from this subset can be routed simultaneously without violating the capacity constraints. The best known approximation results are a quasi-polynomial time-approximation scheme if the task demands are in a quasi-polynomial range Bansal et al., STOC 2006 and a polynomial time (2 + ε)-approximation algorithm Anagnostopoulos et al., SODA 2014. Finding a PTAS for it has remained an important open question.In this paper we make progress towards this goal. When the task densities---defined as the ratio of a task's profit and demand---lie in a constant range, we obtain a PTAS. We also improve the QPTAS of Bansal et al. by removing the assumption that the demands need to lie in a quasi-polynomial range. Our third result is a PTAS for the case where we are allowed to shorten the paths of the tasks by at most an ε-fraction. This is particularly motivated by bandwidth allocation and scheduling applications of our problem if we are allowed to slightly increase the speed of the underlying transmission link/machine. Each of these results critically uses a sparsification lemma which we believe could be of independent interest. The lemma shows that in any (optimal) solution there exists an O(ε)-fraction (measured by weight) of its tasks whose removal creates, on each edge, a slack which is at least as large as the (1/ε)th largest demand using that edge. This slack can then be used to allow slight errors when estimating or rounding quantities arising in the computation.