Improved Algorithms for Scheduling Unsplittable Flows on Paths

In this paper, we investigate offline and online algorithms for rufpp, the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform sizes on a given path with non-uniform edge capacities. rufpp is NP-hard and constant-factor approximation algorithms are known under the no bottleneck assumption (NBA), which stipulates that maximum size of a flow is at most the minimum edge capacity. We study rufpp without the NBA, and present improved online and offline algorithms. We first study offline rufpp for a restricted class of instances called α-small, where the size of each flow is at most α times the capacity of its bottleneck edge, and present an O(log(1/(1-α)))-approximation algorithm. Our main result is an online O(loglog cmax)-competitive algorithm for rufpp for general instances, where cmax is the largest edge capacities, improving upon the previous best bound of O(log cmax) due to Epstein et al. Our result leads to an offline O(min(log n, log m, loglog cmax))-approximation algorithm and an online O(min(log m, loglog cmax))-competitive algorithm for rufpp, where n is the number of flows and m is the number of edges.