Closing the Gap for Makespan Scheduling via Sparsification Techniques

Abstract

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. It has been recently shown that a subexponential running time on 1/epsilon 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 quadratic running time on the exponent. In this paper we obtain an algorithm with an almost-linear dependency on 1/epsilon in the exponent, which is tight under ETH up to logarithmic factors. Our main technical contribution is a new structural result on the configuration-IP integer linear program. 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. We exemplify this by applying our structural results 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 with an almost-linear dependency on 1/epsilon and polynomial in n.