Theory of Computing
-------------------
Title : Minimizing Maximum Flow-Time on Related Machines
Authors : Nikhil Bansal and Bouke Cloostermans
Volume : 12
Number : 14
Pages : 1-14
URL : https://theoryofcomputing.org/articles/v012a014
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 model.
A preliminary version of this paper appeared in the Proceedings of the
18th Internat. Workshop on Approximation Algorithms for Combinatorial
Optimization Problems (APPROX'15), 2015, pp. 85-95.