# Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling

arXiv: https://arxiv.org/abs/2606.13133 · HTML: https://mlsanity.com/paper/2606.13133/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 27 references that are in the map.
- First posted on arXiv 11 Jun 2026.

## Builds on (most cited first, 16 of 16)

- [Competitive caching with machine learned advice](https://mlsanity.com/paper/1802.05399/) (2018)
- [Algorithms with Predictions](https://mlsanity.com/paper/2006.09123/) (2020)
- [Parallelizing the dual revised simplex method](https://mlsanity.com/paper/1503.01889/) (2015)
- [The Primal-Dual method for Learning Augmented Algorithms](https://mlsanity.com/paper/2010.11632/) (2020)
- [Near-Optimal Bounds for Online Caching with Machine Learned Advice](https://mlsanity.com/paper/1910.12172/) (2019)
- [Improving Online Algorithms via ML Predictions](https://mlsanity.com/paper/2407.17712/) (2024)
- [Parsimonious Learning-Augmented Caching](https://mlsanity.com/paper/2202.04262/) (2022)
- [Learning-Augmented Algorithms for Online Linear and Semidefinite Programming](https://mlsanity.com/paper/2209.10614/) (2022)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Approximation Algorithms for Combinatorial Optimization with Predictions](https://mlsanity.com/paper/2411.16600/) (2024)
- [Parsimonious Learning-Augmented Approximations for Dense Instances of NP-hard Problems](https://mlsanity.com/paper/2402.02062/) (2024)
- [Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness](https://mlsanity.com/paper/2402.14847/) (2024)
- [Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems](https://mlsanity.com/paper/2502.00841/) (2025)
- [Improved Approximations for Hard Graph Problems using Predictions](https://mlsanity.com/paper/2505.23967/) (2025)
- [Optimization and Reoptimization in Scheduling Problems](https://mlsanity.com/paper/1509.01630/) (2015)
- [All You Need is an Improving Column: Enhancing Column Generation for Parallel Machine Scheduling via Transformers](https://mlsanity.com/paper/2410.15601/) (2024)

## Abstract (arXiv)

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|Cmax. 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.