  Makespan scheduling on identical machines is one of the most basic and
fundamental packing problems studied in the discrete optimization literature.
It asks for an assignment of $n$ jobs to a set of $m$ identical machines that
minimizes the makespan. The problem is strongly NP-hard, and thus we do not
expect a $(1+\epsilon)$-approximation algorithm with a running time that
depends polynomially on $1/\epsilon$. Furthermore, Chen et al. [3] recently
showed that a running time of $2^{(1/\epsilon)^{1-\delta}}+\text{poly}(n)$ for
any $\delta>0$ would imply that the Exponential Time Hypothesis (ETH) fails. A
long sequence of algorithms have been developed that try to obtain low
dependencies on $1/\epsilon$, the better of which achieves a running time of
$2^{\tilde{O}(1/\epsilon^2)}+O(n\log n)$ [11]. In this paper we obtain an
algorithm with a running time of $2^{\tilde{O}(1/\epsilon)}+O(n\log n)$, which
is tight under ETH up to logarithmic factors on the exponent.
  Our main technical contribution is a new structural result on the
configuration-IP. More precisely, we show the existence of a highly symmetric
and sparse optimal solution, in which all but a constant number of machines are
assigned a configuration with small support. This structure can then be
exploited by integer programming techniques and enumeration. We believe that
our structural result is of independent interest and should find applications
to other settings. In particular, we show how the structure can be applied to
the minimum makespan problem on related machines and to a larger class of
objective functions on parallel machines. For all these cases we obtain an
efficient PTAS with running time $2^{\tilde{O}(1/\epsilon)} + \text{poly}(n)$.

Data Structures and Algorithms