DROPS

Document

DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.85

Minimizing Maximum Flow-time on Related Machines

Authors: Nikhil Bansal and Bouke Cloostermans

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract

We consider the online problem of minimizing the maximum flow-time on related machines. This is a natural generalization of the extensively studied makespan minimization problem to the setting where jobs arrive over time. Interestingly, natural algorithms such as Greedy or Slow-fit that work for the simpler identical machines case or for makespan minimization on related machines, are not O(1)-competitive. Our main result is a new O(1)-competitive algorithm for the problem. Previously, O(1)-competitive algorithms were known only with resource augmentation, and in fact no O(1) approximation was known even in the offline case.

Cite as

Nikhil Bansal and Bouke Cloostermans. Minimizing Maximum Flow-time on Related Machines. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 85-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{bansal_et_al:LIPIcs.APPROX-RANDOM.2015.85,
  author =	{Bansal, Nikhil and Cloostermans, Bouke},
  title =	{{Minimizing Maximum Flow-time on Related Machines}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{85--95},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.85},
  URN =		{urn:nbn:de:0030-drops-52964},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.85},
  annote =	{Keywords: Related machines scheduling, Maximum flow-time minimization, On-line algorithm, Approximation algorithm}
}

Search Results

Documents authored by Cloostermans, Bouke

Minimizing Maximum Flow-time on Related Machines

Abstract

Cite as

Thanks for your feedback!

Could not send message