用预测改进非相关机调度的完工时间，精度高且鲁棒。
Learning-Augmented Approximation for Unrelated-Machines Makespan Scheduling
- 基于重任务分配预测，设计可学习增强的近似算法
- 预测准确时可达(1+ε)近似，误差增大时退化为2倍最坏情况
- 适用于需要高效调度且有历史数据参考的场景
Antoniadis 等人（ICLR 2025）提出了一种将预测信息融入近似求解 NP 难选择问题的框架。尽管方法简洁，却能逼近理论下界，其推广极具吸引力。本文解决该工作提出的开放问题：将此方法拓展至选择问题以外的重要问题，如调度。我们为非相关机最小化完工时间问题 $R\|C_{\max}$ 构建了一个学习增强算法。通过使用对重任务分配的预测，该算法在预测准确时可实现多项式时间 $(1+\varepsilon)$-近似，并随预测误差增大平滑退化至最坏情况 2-近似。最后，我们对该方法进行了实证分析。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。