Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Tight running times for minimum $\ell_q$-norm load balancing: beyond
  exponential dependencies on $1/\epsilon$   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 minimized, where $C_i$ 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 an $(1+\epsilon)$-approximation
algorithm for a strongly NP-hard problem cannot be polynomial on $1/\epsilon$,
unless $\text{P}=\text{NP}$. For most problems in the literature, this
translates into algorithms with running time at least as large as
$2^{\Omega(1/\varepsilon)}+n^{O(1)}$. For the natural scheduling problem above,
we establish the existence of an algorithm which violates this threshold. More
precisely, we design a PTAS that runs in
$2^{\tilde{O}(\sqrt{1/\epsilon})}+n^{O(1)}$ 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 $\epsilon$ and the
number of machines $m$. More precisely, our lower bound only holds when
$m=\Theta(\sqrt{1/\epsilon})$. 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 $1/\epsilon$ if we restrict ourselves
to instances with $m=\Omega(1/\epsilon\log^21/\epsilon)$.

16
The categories of this paper are: stat
32
The categories of this paper are: atom-ph
25
The categories of this paper are: patt-sol
8
The categories of this paper are: hep-ex
23
The categories of this paper are: solv-int
29
The categories of this paper are: funct-an
36
The categories of this paper are: cmp-lg
10
The categories of this paper are: q-bio
12
The categories of this paper are: nucl-th
15
The categories of this paper are: nucl-ex
31
The categories of this paper are: ao-sci
6
The categories of this paper are: astro-ph
2
The categories of this paper are: math
37
The categories of this paper are: supr-con
35
The categories of this paper are: mtrl-th
22
The categories of this paper are: chao-dyn