← 研踪 PaperTrailarXiv:2610.32503 · v2
Pareto-optimal Non-Clairvoyant Scheduling with Predictions
首次提交 2026-10-23 19:26
版本更新 2026-11-04 03:17
雷达观测 2026-11-05 10:08
摘要
We study preemptive single-machine non-clairvoyant scheduling with predictions, where a prediction of the order of the jobs (or of their sizes) is available, and the objective is to minimize the total completion time. An algorithm is $c$-consistent if it is $c$-competitive when the prediction is correct, and $R$-robust if it is $R$-competitive whatever the prediction. Since the introduction of this problem as one of the first examples of learning-augmented algorithms, the best possible trade-off between consistency and robustness has remained open. We determine it exactly for deterministic algorithms. For every $R>2$, we give an $R$-robust algorithm whose consistency is \[ c(R)=R\Big(1-\Big(1-\frac{R+2}{R^2}\Big)^{\frac R{R+2}}\Big), \] and we prove that no deterministic $R$-robust algorithm, with either predicted order or predicted job sizes, has better consistency. In particular, consistency $1+\varepsilon$ is achievable with robustness $\varepsilon^{-1/2}+\frac16+O(\sqrt\varepsilon)$, whereas all previous algorithms required robustness $Θ(1/\varepsilon)$. Our algorithm is greedy: it follows the predicted order as fast as possible, subject to the invariant that the cost paid so far is at most $R$ times the optimum of the instance in which every unfinished job would end immediately. The matching lower bound rests on the observation that every robust deterministic algorithm must satisfy the same invariant along its run on correct predictions. Furthermore, we give a simple randomized algorithm, using predicted sizes, with consistency $1+\varepsilon$ and robustness $(3\varepsilon)^{-1/2}+O(1)$, strictly below the deterministic frontier. The question of determining the Pareto-optimal frontier among randomized algorithms remains open.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v2 · 2026-11-04 03:17 · 最新观测版本
Pareto-optimal Non-Clairvoyant Scheduling with Predictions
We study preemptive single-machine non-clairvoyant scheduling with predictions, where a prediction of the order of the jobs (or of their sizes) is available, and the objective is to minimize the total completion time. An algorithm is $c$-consistent if it is $c$-competitive when the prediction is correct, and $R$-robust if it is $R$-competitive whatever the prediction. Since the introduction of this problem as one of the first examples of learning-augmented algorithms, the best possible trade-off between consistency and robustness has remained open. We determine it exactly for deterministic algorithms. For every $R>2$, we give an $R$-robust algorithm whose consistency is \[ c(R)=R\Big(1-\Big(1-\frac{R+2}{R^2}\Big)^{\frac R{R+2}}\Big), \] and we prove that no deterministic $R$-robust algorithm, with either predicted order or predicted job sizes, has better consistency. In particular, consistency $1+\varepsilon$ is achievable with robustness $\varepsilon^{-1/2}+\frac16+O(\sqrt\varepsilon)$, whereas all previous algorithms required robustness $Θ(1/\varepsilon)$. Our algorithm is greedy: it follows the predicted order as fast as possible, subject to the invariant that the cost paid so far is at most $R$ times the optimum of the instance in which every unfinished job would end immediately. The matching lower bound rests on the observation that every robust deterministic algorithm must satisfy the same invariant along its run on correct predictions. Furthermore, we give a simple randomized algorithm, using predicted sizes, with consistency $1+\varepsilon$ and robustness $(3\varepsilon)^{-1/2}+O(1)$, strictly below the deterministic frontier. The question of determining the Pareto-optimal frontier among randomized algorithms remains open.
查看此版本解读 →查看此版本原文 ↗