CS Paper Radar

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

Sizhe Li, Nicolas Christianson, Tongxin Li

cs.DS ·submitted 2026-10-21 01:10 UTC · v1
theory

Abstract

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Pareto-optimal Non-Clairvoyant Scheduling with Predictions

cs.DS cs.GT ·2026-10-23 ·Ziyad Benomar, Vianney Perchet
theory similarity 0.79
Abstract

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.

0.19

Robust Non-Clairvoyant Scheduling with Classification Models

cs.LG cs.DS ·2026-10-01 ·Anthony Dugois, Vincent Fagnon, Giorgio Lucarelli
similarity 0.71
Abstract

We study the classical single-machine scheduling problem of minimizing the sum of completion times of jobs in a non-clairvoyant setting, where the processing time of each job remains unknown until its completion. This is a hard problem for which no constant competitive algorithm is possible. Inspired by robust optimization and learning-augmented algorithms, we introduce a novel robustness framework that leverages structural information provided by a classification model to overcome this limitation. Specifically, we assume that jobs are partitioned into classes and we have access to the confusion matrix of the classifier, whose entry $(k,\ell)$ indicates the number of jobs predicted to belong to class~$k$ but that actually belong to class~$\ell$. In this manner, we are able to characterize uncertainty as a set of permutations within each predicted class, rather than as a collection of discrete numerical scenarios, avoiding the computational difficulty of classical robust metrics, such as Min-Max and Min-Max Regret. In addition to these worst-case metrics, we also consider the expected objective over all scenarios. We first propose an optimal non-adaptive strategy that is oblivious with respect to all three robust criteria. We then investigate adaptive and randomized algorithms, showing that they can outperform the optimal non-adaptive strategy when the matrix exhibits particular structural properties.

0.43

The Exact Robustness of Smith's Rule with Predicted Processing Times

cs.DS ·2026-10-23 ·Ohad Ayalon, Ilan Reuven Cohen
similarity 0.68
Abstract · 39 pages, 3 figures. Includes full proofs and exact-arithmetic ancillary scripts

Smith's rule orders jobs by their weight-to-processing-time ratios. We study the robustness of its list schedule on identical parallel machines when job $j$ is ordered using a nominal processing time $μ_j$ and its true processing time satisfies $μ_j\leq p_j\leqαμ_j$, where $α\geq1$. We determine the exact worst-case approximation ratio against the clairvoyant optimum, taking the supremum over machine counts. The ratio is an explicit continuous piecewise-algebraic function of $α$. It equals the Kawaguchi--Kyan constant $(1+\sqrt{2})/2$ at $α=1$ and is exactly $\sqrtα$ for $α\geq4$. On one machine the exact ratio is $\sqrtα$. For every fixed machine count, no deterministic nonpreemptive algorithm can improve on this guarantee, even with knowledge of $α$. The proof reduces to a common nominal Smith ratio and endpoint errors. Cutting the list schedule at its minimum final machine load yields a prefix--suffix certificate; two packings of matching lower-bound instances explain the branches below $α=4$. We also prove a nominal-to-robust transfer: any fixed schedule ordered by nominal Smith ratios on each machine, with nominal approximation ratio $1+δ$, has realized ratio at most $\sqrtα+αδ$. A nominal approximation scheme then gives, for every fixed $\varepsilon>0$, a deterministic polynomial-time algorithm independent of $α$ with ratio $(1+\varepsilon)\sqrtα$ simultaneously for $1\leqα\leq4$.

0.32

Consistency-Robustness Tradeoffs for Strategyproof Scheduling with Predictions

cs.GT ·2026-09-12 ·Hau Chan, Jianan Lin, Chenhao Wang
theory similarity 0.67
Abstract

We study strategyproof scheduling on \(n\) unrelated machines with predictions. Each machine is controlled by an agent with privately known processing times, while the mechanism receives a public prediction of the processing-time matrix before the agents report. The objective is to minimize the makespan subject to strategyproofness. We measure performance by consistency, the approximation guarantee for correct predictions, and robustness, the worst-case guarantee for arbitrary predictions. We introduce \textsc{EdgeSkip}, a deterministic strategyproof member of the class of job-wise weighted mechanisms. Such mechanisms allocate each job independently using prediction-dependent weights. Using a polynomial-time \(2\)-approximate reference schedule computed from the prediction and a standard tradeoff parameter, \textsc{EdgeSkip} is \(4\)-consistent and \((2n-2)\)-robust, improving on the \((6,2n)\) guarantee of Balkanski, Gkatzelis, and Tan. Without computational restrictions, \textsc{EdgeSkip} with an optimal reference schedule is \(C\)-consistent and \(\max\{n,(n-1)C/(C-1)\}\)-robust for every \(C>1\). We prove a matching information-theoretic lower bound for all job-wise weighted mechanisms, thereby determining the exact consistency--robustness tradeoff for this class. For arbitrary deterministic strategyproof mechanisms, we establish the robustness lower bound \(\max\{n,C/(C-1)\}\) for every \(C>1\). We also study an error-tolerant variant and improve upon prior guarantees. Experiments demonstrate that our mechanisms achieve good empirical performance.

0.36

Speed-Robust Scheduling for Total Completion Time

cs.DS cs.DM ·2026-11-16 ·Moritz Buchem, Nicole Megow, Morten Weber
similarity 0.65
Abstract

We study two-stage speed-robust scheduling for minimizing total completion time. Jobs must be partitioned into $M$ bags before an adversary reveals the speeds of at most $M$ machines. Each bag is then assigned to one available machine, and the jobs on each machine may be processed in any order independent of the bags. We compare with an optimal schedule that knows the speeds in advance and assigns jobs individually. This model has been studied for makespan minimization. We initiate its study for total completion time, as suggested by Stein and Zhong (TALG 2020). For an unknown number of identical machines, we show that the optimal deterministic robustness factor is exactly~$13/12$, both for unit-size jobs and for arbitrary processing times. For infinitesimally small jobs, the factor lies between $31/30\approx1.0333$ and $28/27\approx1.0370$, well below the optimal makespan factor of about $1.2071$. General speeds make the problem strictly harder: no deterministic algorithm is better than $1.2669$-robust, already for infinitesimally small jobs. We give a $25/16$-robust algorithm for arbitrary processing times and improve the guarantee to $1681/1152\approx1.4592$ for infinitesimally small jobs. Our main tools are a layer decomposition that extends guarantees from unit-size jobs to arbitrary processing times when one assignment satisfies them for every prefix in non-increasing processing-time order, and a threshold analysis of the bag counts produced by greedy assignment rules.

0.18

Non-Clairvoyant Scheduling is Hard Even for Trees

cs.DS ·2026-10-07 ·Kunal Agrawal, Owen Druzgal, Milind Prabhu, Jinhao Zhao
theory similarity 0.65
Abstract

We study online scheduling of parallel jobs on $m$ identical processors to minimize maximum flow time. Each arriving job is represented by a directed acyclic graph (DAG) whose vertices are unit-time subjobs and whose edges specify precedence constraints. We consider non-clairvoyant algorithms: the DAG is not known when a job arrives, and each subjob is revealed only when it becomes ready. Agrawal, Moseley, Newman, and Pruhs (SPAA 2024) showed that First-In-First-Out (FIFO) has competitive ratio $Ω(\log m)$ even when every job is an out-tree. They also proved that FIFO is $O(\log m)$-competitive in several natural settings and asked whether this guarantee extends to general instances. More broadly, they asked whether any non-clairvoyant algorithm can be $O(1)$-competitive. We answer both questions in the negative by proving a lower bound of $Ω(\min\{m,\mathrm{OPT}\})$ for every non-clairvoyant online algorithm, where $\mathrm{OPT}$ is the maximum flow time of an optimal offline schedule. In particular, every non-clairvoyant algorithm has competitive ratio $Ω(m)$ on some instance with $\mathrm{OPT} \ge m$. The lower bound holds even when every job is an out-forest. We complement these lower bounds with an asymptotically optimal non-clairvoyant algorithm. FIFO is $O(m)$-competitive, but can have competitive ratio $Ω(m)$ even when $\mathrm{OPT}=O(1)$. For instances with small $\mathrm{OPT}$, we design a Small-Frontier-First algorithm that is $O(\mathrm{OPT})$-competitive. Combining the two algorithms yields an $O(\min\{m,\mathrm{OPT}\})$-competitive non-clairvoyant algorithm.

0.34

Robust Approximation and the Arity Barrier at Width Two

cs.CC ·2026-09-29 ·Nathan Benedetto Proença, Koppány István Encz, Monaldo Mastrolilli
theory similarity 0.63
Abstract

Zwick's algorithm for Horn satisfiability shows that constraints of unbounded arity can admit a robust approximation guarantee independent of the arity. For finite constraint languages, Barto and Kozik proved that robust approximability is characterized by bounded width. We ask whether arity-independent robustness persists beyond width one and show that it fails already at width two. For Majority-closed Boolean linear constraints of maximum arity $k \ge 2$, we give a randomized polynomial-time algorithm that, without knowing $\varepsilon$, violates an expected $O(\sqrt{\varepsilon \log k})$ fraction of the constraint weight on $(1-\varepsilon)$-satisfiable instances. Under the Unique Games Conjecture (UGC), a matching NP-hardness lower bound of $Ω(\sqrt{\varepsilon \log k})$ holds in an explicit parameter regime. Under this assumption, the bounded-width characterization therefore does not extend uniformly to constraints of unbounded arity. The algorithm rounds a degree-eight Sum-of-Squares (SoS) relaxation with a single Gaussian threshold. Since polynomial size alone does not make SoS solvable in polynomial bit complexity, we construct complete truncated Groebner bases for the soft Majority ideal and show that, at every fixed degree $2d$, the relaxation can be optimized to any rational accuracy in polynomial time with exactly feasible solutions, and degree-$2d$ SoS proofs can be found after an additive perturbation at degree at most $4d+10$. The lower bound combines Raghavendra's gap-to-hardness theorem with an integrality gap on a Gaussian star, analyzed via the Isaksson-Mossel theorem that parallel halfspaces maximize the joint membership probability of exchangeable Gaussians.

0.44

Consistent Submodular Maximization with Full Foresight

cs.DS cs.LG ·2026-11-04 ·Eric Balkanski, Paul Dütting, Federico Fusco, Silvio Lattanzi, Ashkan Norouzi-Fard +2 more
theory similarity 0.62
Abstract

Online algorithms with bounded recourse face three intertwined obstacles: uncertainty about the future, computational limits, and a limited budget for changes. We ask a fundamental question that separates consistency from the other two: what does solution stability cost when the entire future is known and computation is unlimited? We answer this question for monotone submodular maximization, where an algorithm must maintain a solution of at most $k$ arrived elements, with a constant number of changes per step. We determine the optimal approximation thresholds: $3/4$ for deterministic algorithms and $ξ^\star \approx 0.7942$ for randomized algorithms. For every $\varepsilon>0$, we get within $\varepsilon$ of these thresholds with worst-case recourse polynomial in $1/\varepsilon$, independent of $k$ and the stream length. We prove matching impossibility results even for coverage functions. We attain the sharp bounds by optimally balancing two opposing forces: preparing for future arrivals and protecting the current solution. For randomized algorithms, we use addition robustness against prefixes of the known future, which we analyze tightly via an interval-selection problem. For deterministic algorithms, we introduce certificates, paths in a fractional relaxation that maintain high value, which we round into an update schedule.

0.44