Proof of the density threshold conjecture for pinwheel scheduling
- 1Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan
Abstract
In the pinwheel scheduling problem, each task i is associated with a positive integer ai called its period, and we want to (perpetually) schedule one task per day so that each task i is performed at least once every ai days. An obvious necessary condition for schedulability is that the density, defined as the sum of execution rates 1/ai, does not exceed 1. We prove that all instances with density not exceeding 5/6 are schedulable, as was conjectured by Chan and Chin in 1993. Like some of the known partial progress toward the conjecture, our proof involves computer search for schedules for a large but finite set of instances. A key idea in our reduction to these finite cases is to generalize the problem to fractional (noninteger) periods in an appropriate way. As byproducts of our ideas, we obtain a simple proof that every instance with two distinct periods and density at most 1 is schedulable, as well as a fast algorithm for the bamboo garden trimming problem with approximation ratio 4/3.
Related
- Nonlinear Dose–Response Association Between Exercise Intensity and Urinary Liver-Type Fatty Acid-Binding Protein in Young Men: A Piecewise Threshold Analysis
- Type I and III interferons differentially encode inflammatory gene activation through threshold control of ISGF3 dynamics
- Multivalent Scaffolding by XIST E-Repeats Tunes RNA Binding Protein Cooperativity and Lowers the Phase Separation Threshold
- e^-2 Threshold for Bistability in Non-equilibrium Sorting of Biomolecular Condensates
- Why are some neurons spared in neurodegeneration? Cellular subtype identity maintenance as a candidate threshold-setting mechanism
BibTeX
@article{kawamura2026proof,
title = {{Proof of the density threshold conjecture for pinwheel scheduling}},
author = {Akitoshi Kawamura},
journal = {Proceedings of the National Academy of Sciences of the United States of America},
year = {2026},
month = aug,
doi = {10.1073/pnas.2530214123},
url = {https://doi.org/10.1073/pnas.2530214123},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - JOUR
TI - Proof of the density threshold conjecture for pinwheel scheduling
AU - Akitoshi Kawamura
PY - 2026
DA - 2026/08/07
JO - Proceedings of the National Academy of Sciences of the United States of America
DO - 10.1073/pnas.2530214123
UR - https://doi.org/10.1073/pnas.2530214123
AB - In the pinwheel scheduling problem, each task i is associated with a positive integer ai called its period, and we want to (perpetually) schedule one task per day so that each task i is performed at least once every ai days. An obvious necessary condition for schedulability is that the density, defined as the sum of execution rates 1/ai, does not exceed 1. We prove that all instances with density not exceeding 5/6 are schedulable, as was conjectured by Chan and Chin in 1993. Like some of the known partial progress toward the conjecture, our proof involves computer search for schedules for a large but finite set of instances. A key idea in our reduction to these finite cases is to generalize the problem to fractional (noninteger) periods in an appropriate way. As byproducts of our ideas, we obtain a simple proof that every instance with two distinct periods and density at most 1 is schedulable, as well as a fast algorithm for the bamboo garden trimming problem with approximation ratio 4/3.
SN - 0027-8424
SN - 1091-6490
ER -