📖
Near-Optimal Consistency-Robustness Bounds for Non-Clairvoyant Scheduling
Sizhe Li, Nicolas Christianson, Tongxin Li

Near-Optimal Consistency-Robustness Bounds for Non-Clairvoyant Scheduling

Science & Mathematics Published 2026 Verification Pending

Overview & Synopsis

We study the problem of characterizing the optimal consistency--robustness tradeoff for single-machine non-clairvoyant scheduling with predicted processing times. For a fixed number of jobs $n$, Wei and Zhang (2020) established a lower bound on the achievable consistency--robustness tradeoff which is known to be tight only in a few restrictive cases, leaving the optimal tradeoff for general $n$ unresolved. A different worst-case-$n$ regime was introduced by Benomar et al. (2025), who applied the former work's construction to show that for $λ\in (0, 1)$, any $(1+λ)$-consistent algorithm must be $1 + Ω(\sqrt{1/λ})$-robust. On the other hand, the best known upper bound gives $(1+λ)$-consistency and $1+O(1/λ)$-robustness, leaving a polynomial gap. In this work, we develop a new lower bound using a multi-stage adversarial construction and a new algorithm that together give a near-optimal characterization of the consistency--robustness tradeoff: for every $n$, our upper bound is within a multiplicative factor $3/2$ of our lower bound, and thus our algorithm is within a multiplicative factor $3/2$ of the online optimal. In particular, our lower bound shows that any $(1+λ)$-consistent algorithm must have robustness at least $1/\sqrtλ$ as $n \to \infty$, while our algorithm achieves robustness at most $\frac{1}{2}+\sqrt{\frac{5}{4}+1/λ}$ for any $n$, matching the lower bound in the leading term as $λ\downarrow 0$; our upper bound also closes the polynomial gap in the worst-case-$n$ regime. We additionally show how our algorithm can be made error-tolerant, preserving the near-optimal consistency-robustness tradeoff while incurring only slightly degraded performance under bounded prediction errors.

Indexed from repository: arXiv (arxiv.org)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Near-Optimal Consistency-Robustness Bounds for Non-Clairvoyant Scheduling
Author / Organization Sizhe Li, Nicolas Christianson, Tongxin Li
Subject & Discipline cs.DS
Categories Science & Mathematics
Publication Year 2026
License / Rights arXiv Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website arXiv (arxiv.org)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-268938
Original Source Link Visit Source Page on arxiv.org »