Tight Running Times for Minimum ℓq-Norm Load Balancing: Beyond Exponential Dependencies on 1/ϵ

We consider a classical scheduling problem on m identical machines. For an arbitrary constant [Formula: see text], the aim is to assign jobs to machines such that [Formula: see text] is minimized, where [Formula: see text] is the total processing time of jobs assigned to machine i. It is well known that this problem is strongly NP-hard. Under mild assumptions, the running time of a [Formula: see text]-approximation algorithm for a strongly NP-hard problem cannot be polynomial on [Formula: see text], unless [Formula: see text]. For most problems in the literature, this translates into algorithms with running time at least as large as [Formula: see text]. For the natural scheduling problem above, we establish the existence of an algorithm that violates this threshold. More precisely, we design a PTAS that runs in [Formula: see text] time. This result is in sharp contrast to the closely related minimum makespan variant, where an exponential lower bound is known under the exponential time hypothesis (ETH). We complement our result with an essentially matching lower bound on the running time, showing that our algorithm is best possible under ETH. The lower bound proof exploits new number-theoretical constructions for variants of progression-free sets, which might be of independent interest. Furthermore, we provide a fine-grained characterization on the running time of a PTAS for this problem depending on the relation between [Formula: see text] and the number of machines m. More precisely, our lower bound only holds when [Formula: see text]. Better algorithms that go beyond the lower bound exist for other values of m. In particular, there even exists an algorithm with running time polynomial in [Formula: see text] if we restrict ourselves to instances with [Formula: see text]. Funding: This research was supported by the Center for Mathematical Modeling BASAL [Fund FB210005], ANID-Chile, and ANID/Fondecyt [Regular 1221460]. National Science Foundation China [12271477], National Science Foundation [1756014].