Tight running times for minimum ${\ell }_q$-norm load balancing: beyond exponential dependencies on $1/\epsilon$

Lin Chen, Liangde Tao, José Verschae

We consider a classical scheduling problem on $m$ identical machines. For an arbitrary constant $q>1$, the aim is to assign jobs to machines such that ${\sum }_{i=1}^m{C}_i^q$ is minim…