  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 $\alpha$-small, where the size
of each flow is at most $\alpha$ times the capacity of its bottleneck edge, and
present an $O(\log(1/(1-\alpha)))$-approximation algorithm. Our main result is
an online $O(\log\log c_{\max})$-competitive algorithm for rufpp for general
instances, where $c_{\max}$ is the largest edge capacities, improving upon the
previous best bound of $O(\log c_{\max})$ due to Epstein et al. Our result
leads 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 rufpp, where $n$ is the number of flows and $m$ is the number of
edges.

Data Structures and Algorithms