Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper extends the learning-augmented framework proposed by Antoniadis et al. to the unrelated-machines makespan scheduling problem, demonstrating its applicability beyond selection problems. By leveraging predictions of heavy job assignments, the authors achieve a polynomial-time $(1+\varepsilon)$-approximation for the makespan minimization problem, with a graceful degradation to a worst-case 2-approximation under prediction errors. Empirical analyses validate the effectiveness of the proposed algorithm, highlighting its practical relevance in scheduling scenarios.
Achieving a polynomial-time $(1+\varepsilon)$-approximation for unrelated-machines scheduling could revolutionize how we tackle NP-hard scheduling problems with predictive insights.
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.