Piotr Berman, Moses Charikar, Marek Karpinski

We consider the problem of scheduling permanent jobs on related machines

in an on-line fashion. We design a new algorithm that achieves the

competitive ratio of $3+\sqrt{8}\approx 5.828$ for the deterministic

version, and $3.31/\ln 2.155 \approx 4.311$ for its randomized variant,

improving the previous competitive ratios ...
more >>>