Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling
For scheduling practitioners, this provides a practical algorithm that leverages predictions to improve performance while maintaining worst-case guarantees.
The authors extend a learning-augmented framework to the unrelated-machines makespan scheduling problem, achieving a polynomial-time (1+ε)-approximation with accurate predictions that degrades to a 2-approximation as prediction error increases.
Recently, Antoniadis et al. (ICLR 2025) proposed a framework for incorporating predictions to approximate NP-hard selection problems. Despite its simplicity, this approach tightly matches theoretical lower bounds, making its generalization highly compelling. We address an open question raised in the work of Antoniadis et al., concerning the extension of this approach to other important problems outside the class of selection problems, such as scheduling. We develop a learning-augmented algorithm for the makespan minimization problem on unrelated machines, denoted by $R\|C_{\max}$. By using predictions of heavy job assignments, we achieve a polynomial-time $(1+\varepsilon)$-approximation for accurate predictions that smoothly degrades to a worst-case 2-approximation as the error increases. We conclude our work with an empirical analysis of our method.