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.