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.