{"id":"arxiv/2606.27104","url":"https://arxiv.org/abs/2606.27104","tags":["cs.DM","cs.DS","math.CO"],"score":0,"title":"Proof of the Density Threshold Conjecture for Pinwheel Scheduling","domain":"cs.DM","source":"arxiv","authors":["Akitoshi Kawamura"],"reviews":0,"subject":"cs.DM","summary":"In the pinwheel scheduling problem, each task $i$ is associated with a positive integer $a_i$ called its period, and we want to (perpetually) schedule one task per day so that each task $i$ is performed at least once every $a_i$ days. An obvious necessary condition for schedulability is that the density, defined as the sum of execution rates $1/a_i$, 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 towards the conjecture, our proof involves computer search…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-25","reactions":{}}