Proof of the Density Threshold Conjecture for Pinwheel Scheduling
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.27104
curl -X POST /api/v1/records/arxiv/2606.27104/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.27104/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'