Improved Algorithms for Scheduling Unsplittable Flows on Paths.

We investigate offline and online algorithms for Round - UFPP , the problem of minimizing the number of rounds required to schedule a set of unsplittable flows of non-uniform size on a given path with heterogeneous edge capacities. Round - UFPP is known to be NP-hard and there are constant-factor approximation algorithms under the no bottleneck assumption (NBA), which stipulates that maximum size of any flow is at most the minimum global edge capacity. In this work, we present improved online and offline algorithms for Round - UFPP without the NBA. We first study offline Round - UFPP 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. Next, our main result is an online O (log log c max) -competitive algorithm for Round - UFPP where c max is the largest edge capacity, improving upon the previous best bound of O (log c max) due to Epstein et al. (SIAM J Discrete Math 23(2):822–841, 2009). These new results lead to an offline O (min (log n , log m , log log c max)) -approximation algorithm and an online O (min (log m , log log c max)) -competitive algorithm for Round - UFPP , where n is the number of flows and m is the number of edges. [ABSTRACT FROM AUTHOR]