Abstract

In this talk we will briefly discuss online makespan minimization on unrelated machines. We will describe how one can obtain a 2+eps competitive solution with only an average of logarithmically many re-assignments per job, almost matching the best known offline approximation algorithm for this problem.