
arXiv: 1708.00143
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(\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.
FOS: Computer and information sciences, Deterministic scheduling theory in operations research, unsplittable flows, interval scheduling, Online algorithms, optical routing, Approximation algorithms, 004, Computer Science - Data Structures and Algorithms, Unsplittable flows, Analysis of algorithms, Online algorithms; streaming algorithms, Data Structures and Algorithms (cs.DS), Interval coloring, scheduling, Flow scheduling, ddc: ddc:004
FOS: Computer and information sciences, Deterministic scheduling theory in operations research, unsplittable flows, interval scheduling, Online algorithms, optical routing, Approximation algorithms, 004, Computer Science - Data Structures and Algorithms, Unsplittable flows, Analysis of algorithms, Online algorithms; streaming algorithms, Data Structures and Algorithms (cs.DS), Interval coloring, scheduling, Flow scheduling, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 0 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
