Fast monotone 3-approximation algorithm for scheduling related machines

scheduling $n$ jobs to $m$ machines of different speeds s.t. the
makespan is minimized ($Q||C_{\max}$). We provide a fast and simple,
deterministic \emph{monotone} 3-approximation algorithm for $Q||C_{\max}.$
Monotonicity is relevant in the context of \emph{truthful mechanisms}: when each
machine speed is only known to the machine itself, we need to motivate that
machines declare their true speeds to the scheduling mechanism. As shown by
Archer and Tardos, such motivation is possible only if the scheduling algorithm
used by the mechanism is monotone. The best previous monotone algorithm that is
polynomial in $m,$ was a 5-approximation by Andelman et al.
A \emph{randomized} 2-approximation method, satisfying
a weaker definition of truthfulness, is given by Archer. As a core result, we
prove the conjecture of Auletta et al., that the greedy algorithm ({\sc Lpt})
is monotone if machine speeds are all integer powers of~2.