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 >>>

We prove that hashing $n$ balls into $n$ bins via a random matrix over $GF(2)$ yields expected maximum load $O(\log n / \log \log n)$. This matches the expected maximum load of a fully random function and resolves an open question posed by Alon, Dietzfelbinger, Miltersen, Petrank, and Tardos (STOC ... more >>>