Fast Makespan Minimization via Short ILPs

Abstract

Short integer linear programs are programs with a relatively small number of constraints. We show how recent improvements on the running-times of solvers for such programs can be used to obtain fast pseudo-polynomial time algorithms for makespan minimization on a fixed number of parallel machines, and other related variants. The running times of our algorithms are all of the form $\tilde{O}(p_{\max }^{O(1)}+n)$ or $\tilde{O}(p_{\max }^{O(1)}\cdot n)$, where $p_{\max }$ is the maximum processing time in the input. These improve upon the time complexity of previously known algorithms for moderate values of $p_{\max }$.