Online and Random-order Load Balancing Simultaneously
Marco Molinaro (PUC-Rio)

We consider the problem of online load balancing under $\ell_p$-norms: sequential jobs need to be assigned to one of the machines and the goal is to minimize the $\ell_p$-norm of the machine loads. This generalizes the classical problem of scheduling for makespan minimization (case $\ell_{\infty}$) and has been thoroughly studied. We provide algorithms with simultaneously optimal guarantees for the worst-case model as well as for the random-order (i.e. secretary) model, where an arbitrary set of jobs comes in random order. A crucial component for this result that we will try to highlight in the talk is a connection between smoothings of $\ell_p$ norms, the so-called Online Linear Optimization problem, and the expected norm of sums of random vectors.