2026-08-17 京都大学
＜関連情報＞
- https://www.kyoto-u.ac.jp/ja/research-news/2026-08-17
- https://www.pnas.org/doi/10.1073/pnas.2530214123
- https://arxiv.org/abs/2510.06533
輪番割当問題の密度閾値予想の証明 Proof of the density threshold conjecture for pinwheel scheduling
Akitoshi Kawamura
Proceedings of the National Academy of Sciences Published: August 7, 2026
DOI:https://doi.org/10.1073/pnas.2530214123
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.
被覆型輪番割当における最良の密度限界の計算機援⽤証明 A Computer-Assisted Proof of the Optimal Density Bound for Pinwheel Covering
Akitoshi Kawamura, Yusuke Kobayashi
arXiv last revised 18 Nov 2025 (this version, v2)
DOI:https://doi.org/10.48550/arXiv.2510.06533
Abstract
In the covering version of the pinwheel scheduling problem, a daily task must be assigned to agents under the constraint that agent i can perform the task at most once in any ai-day interval. In this paper, we determine the optimal constant α∗=1.264… such that every instance with ∑i1/ai≥α∗ is schedulable. This resolves an open problem posed by Soejima and Kawamura (2020). Our proof combines Kawamura’s (2024) techniques for the packing version with new mathematical insights, along with an exhaustive computer-aided search that draws on some ideas from Gąsieniec, Smith, and Wild (2022).
