# Non-Clairvoyant Scheduling is Hard Even for Trees

Preprint · Kunal Agrawal, Owen Druzgal, Milind Prabhu, Jinhao Zhao

- Archive id: arxiv:2610.11006
- Published: 2026-10-07
- arXiv: https://arxiv.org/abs/2610.11006
- Citations: 0
- Source URL: https://arxiv.org/abs/2610.11006
- PDF: https://arxiv.org/pdf/2610.11006
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Algorithms & Complexity Breakthroughs](https://space-kitty.com/topics/algorithms-complexity)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.