CS Paper Radar

Non-Clairvoyant Scheduling is Hard Even for Trees

Kunal Agrawal, Owen Druzgal, Milind Prabhu, Jinhao Zhao

cs.DS ·submitted 2026-10-07 23:40 UTC · v1
theory

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.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-10-21 ·Sizhe Li, Nicolas Christianson, Tongxin Li
theory similarity 0.65
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.

0.45

Pareto-optimal Non-Clairvoyant Scheduling with Predictions

cs.DS cs.GT ·2026-10-23 ·Ziyad Benomar, Vianney Perchet
theory similarity 0.64
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

Online Submodular Welfare Maximization: Computation is not the Bottleneck

cs.DS math.OC ·2026-10-12 ·Rajan Udwani, David Wajc
publishedhighly cited similarity 0.63
Abstract · In FOCS 2026

We revisit the online submodular welfare maximization problem (OSW), a vast generalization of numerous well-studied online allocation problems, including online bipartite matching, display ads and AdWords. A natural greedy OSW algorithm achieves a competitive ratio of $1/2$ [LLN06], and $1-1/e$ under i.i.d. arrivals [KPV13]. Both bounds are tight for polynomial-time algorithms unless NP=RP [KPV13]. The information-theoretic limits for OSW, in contrast, remained open. This prompted researchers to ask for tighter upper bounds [Mehta13] or conjecture the existence of better-competitive (slow) algorithms [Huang23, LTX+23, CHS24, Huang2024, HTW24}. We resolve Mehta's question and refute the subsequent conjectures, proving that the greedy algorithm is in fact tight for both adversarial and i.i.d. arrivals, regardless of computation time. Seemingly contradicting recent $(1-1/e)$-competitive fractional algorithms for OSW [HJP+24,Patton26], we show that this impossibility even holds for fractional algorithms, provided their outputs correspond to marginals that are roundable in hindsight. Conceptually, our proofs can be seen as identifying that a bottleneck for OSW, even under (deterministic) adversarial arrivals, is the inherently random notion of correlation gap [ADSY12].

0.55

Single-Machine Guarantees on Unrelated Machines and Beyond: Proportional Fairness for Nonclairvoyant Polytope Scheduling

cs.DS ·2026-10-23 ·Sven Jäger, Alexander Lindermayr, Bart Zondervan
theory similarity 0.62
Abstract · Shortened abstract

The Polytope Scheduling Problem (PSP) is a general framework for preemptive scheduling in which feasible instantaneous job allocations form a packing polytope. In the nonclairvoyant online setting, Proportional Fairness (PF), a practical allocation rule rooted in market theory, is the leading general-purpose algorithm. On a single machine, PF coincides with weighted Round-Robin, which is $2$-competitive for weighted completion time with uniform release dates (optimal for nonclairvoyant algorithms) and $(2+\varepsilon)$-speed $O(1/\varepsilon)$-competitive for weighted flow time. Known guarantees beyond a single machine are weaker. This raises a central question: Are these heterogeneous environments intrinsically harder than a single machine under nonclairvoyance? We show that they are not: PF retains both single-machine guarantees on the novel class of support-submodular polytopes, which includes unrelated machines and polymatroids. On unrelated machines, this refutes a belief (JACM'18, SODA'25) that PF is not $O(1)$-speed $O(1)$-competitive for weighted flow time. Our main technical contribution is an equivalent characterization: a polytope is support submodular if and only if, for all job weights, the optimal weighted completion time is concave in the processing requirements. This structural insight underlies both guarantees. For general PSP, the picture changes: we give the first lower bound above $2$, showing that every randomized nonclairvoyant algorithm has a competitive ratio of at least $2+10^{-5}$ for weighted completion time, even with uniform release dates. On the positive side, we substantially improve the best known guarantee for weighted completion time from $27$ (SICOMP'26) to $4$ via a new dual-fitting analysis of PF. For weighted flow time, we show that PF achieves the first $O(1)$-speed $O(1)$-competitive nonclairvoyant guarantee for graph scheduling.

0.27

Hardness of Online Directed Steiner Network

cs.DS ·2026-09-18 ·Gary Hoppenworth, Yaowei Long, Sepideh Mahabadi, Jakub Tarnawski
similarity 0.61
Abstract

In the Directed Steiner Network (DSN) problem we are given a directed graph and a set of demands $(s_i,t_i)$, and asked to find a cheap subgraph connecting each terminal pair. In its online version, the demands arrive online and must be served by buying edges irrevocably. DSN is a fundamental hard problem in network design, heavily studied in both the offline and the online setting. Offline, it has a superpolylogarithmic hardness of approximation. However, offline hardness says nothing about online algorithms, which are computationally unrestricted. It has been an open question whether uncertainty itself (needing to commit to a solution without knowing future demands) rules out polylogarithmic-competitive online algorithms. In this work, we show the first such unconditional, information-theoretic hardness. Namely, we give an $\exp\!\bigl(Ω(\sqrt{\log n})\bigr)$ bound on the competitive ratio, which holds even for randomized algorithms against an oblivious adversary, and on unit-cost DAGs. Our proof uses a novel connection between online network design and algebraic coding theory. We encode requests using a hidden low-degree polynomial, whose past evaluations reveal nothing about future ones. We then use list-recovery bounds to show that an algorithm cannot make cheaply reusable decisions without knowing those future evaluations.

0.18

Online Algorithms with a Sample: Tight Bounds and Adversarial Robustness

cs.DS ·2026-09-18 ·Anish Hebbar, Ravi Kumar, Roie Levin, Joseph, Naor +1 more
similarity 0.61
Abstract

Suppose an online algorithm is given an unbiased $p$-sample of its input as offline advice; can the algorithm exploit the sample to achieve beyond-worst-case performance? We study this online algorithms with a sample (OAS) model. We show a tight $O\left(\log (1/p) \cdot \log m + \log n\right)$-competitive algorithm for set cover, exponentially improving upon the $O\left(1/p \cdot \log (mn)\right)$ guarantee of Gupta et al. (SODA'24) and answering an open question therein. Our techniques extend to covering integer programs and non-metric facility location, also yielding tight bounds for these problems. Further, we give an $O(\log (1/p)/ \log \log (1/p))$-competitive algorithm for metric facility location, answering an open question of Argue et al. (NeurIPS'22). We then introduce and study the robust variant of the OAS model, in which an adversary is allowed to arbitrarily modify $k$ elements of the $p$-sample. For set cover, covering integer programs, and non-metric facility location, we obtain a tight competitive ratio of $O\left(\log (k/p) \cdot \log m + \log n\right)$. For metric facility location and Steiner tree, we obtain tight competitive ratios of $O\left(\log (k/p) / \log \log (k/p) \right)$ and $O\left(\log (k/p)\right)$ respectively. To the best of our knowledge, these are the first results for robust algorithms in the OAS setting.

0.19

Incremental Minimum Spanning Trees on a Napkin

cs.DS ·2026-11-03 ·Lucian Bicsi, Adrian Budău
similarity 0.60
Abstract · 20 pages, 5 figures, 3 tables

In the incremental minimum spanning forest problem, weighted edges arrive one at a time. After each insertion we must report the edge that leaves the minimum spanning forest, and queries ask for the bottleneck distance of two vertices: the smallest possible maximum edge cost on a path between them. Link-cut trees solve both in $O(\log n)$ amortized time. In 2021 we wrote the folklore BottleneckTree, a short competitive-programming structure that stores one parent pointer and one cost per vertex, and conjectured that it also runs in $O(\log n)$ amortized time. We show that this conjecture is false: on a family of inputs, its amortized cost per operation is $Ω(\sqrt{n})$. We then present a structure with the same state, two arrays and a single loop, and prove that it runs in $O(\log n)$ amortized time per insertion and per query. Unlike the AM-tree of Ding, Gu and Sun, which attains the same bound, it stores no subtree sizes and maintains no balance invariant. For a connected graph with distinct costs, the structure can be viewed as an implicit link-cut tree on the Kruskal reconstruction tree: each rotation corresponds to exactly one preferred-child change, and each skip acts on a stale path-parent pointer. In experiments it is 1.3-2.1 times faster than the folklore BottleneckTree on insertions, up to 480 times faster on its adversarial input, and 6.3-16 times faster than an explicit link-cut tree.

0.32

Tight Bounds for Downward-Closed Prophet and Secretary Problems

cs.GT cs.DS ·2026-11-12 ·Hanrui Zhang
similarity 0.60
Abstract

We study online selection problems subject to arbitrary downward-closed feasibility constraints, under different arrival orders, with different distributional assumptions. We establish the following bounds: (1) $Θ(\log^2 n / \log \log n)$ for the standard (adversarial-order) prophet problem, (2) $Ω(\log n)$ for the (Bayesian, random-order) prophet secretary problem, and by extension, for the standard (prior-free, random-order) secretary problem, and (3) $O(\log n / \log \log n)$ for the free-order prophet problem. Together with complementary bounds established in prior work, these results pin down the asymptotically tight competitive ratios for all these variants of prophet and secretary problems subject to downward-closed constraints. Our results refine and reinforce the big-decisions-first principle by Rubinstein and Singla [2026], establishing a superconstant separation between the random-order and free-order models.

0.14