2026-08-11T00:06:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8229 2024-03-06T10:41:51Z ddc:004 open_access

Improved Algorithms for Scheduling Unsplittable Flows on Paths Jahanjou, Hamidreza Kantor, Erez Rajaraman, Rajmohan Approximation algorithms Online algorithms Unsplittable flows Interval coloring Flow scheduling In this paper, 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 sizes on a given path with non-uniform edge capacities. Round-UFPP 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 Round-UFPP without the NBA, and present improved online and offline algorithms. We first study offline Round-UFPP 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 cmax)-competitive algorithm for Round-UFPP for general instances, where cmax is the largest edge capacities, improving upon the previous best bound of O(log cmax) due to [16]. Our result leads to an offline O(min(log n, log m, log log cmax))- approximation algorithm and an online O(min(log m, log log cmax))-competitive algorithm for Round-UFPP, where n is the number of flows and m is the number of edges. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hamidreza Jahanjou and Erez Kantor and Rajmohan Rajaraman 2017 Is Part Of LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2017.49 urn:nbn:de:0030-drops-82292 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.49 eng https://creativecommons.org/licenses/by/3.0/legalcode