DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.49

Improved Algorithms for Scheduling Unsplittable Flows on Paths

Authors: Hamidreza Jahanjou, Erez Kantor, and Rajmohan Rajaraman

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract

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.

Cite as

Hamidreza Jahanjou, Erez Kantor, and Rajmohan Rajaraman. Improved Algorithms for Scheduling Unsplittable Flows on Paths. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 49:1-49:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jahanjou_et_al:LIPIcs.ISAAC.2017.49,
  author =	{Jahanjou, Hamidreza and Kantor, Erez and Rajaraman, Rajmohan},
  title =	{{Improved Algorithms for Scheduling Unsplittable Flows on Paths}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{49:1--49:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.49},
  URN =		{urn:nbn:de:0030-drops-82292},
  doi =		{10.4230/LIPIcs.ISAAC.2017.49},
  annote =	{Keywords: Approximation algorithms, Online algorithms, Unsplittable flows, Interval coloring, Flow scheduling}
}

Search Results

Documents authored by Jahanjou, Hamidreza

Improved Algorithms for Scheduling Unsplittable Flows on Paths

Abstract

Cite as

Thanks for your feedback!

Could not send message