Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2510.06533 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912715962843136 |
|---|---|
| author | Kawamura, Akitoshi Kobayashi, Yusuke |
| author_facet | Kawamura, Akitoshi Kobayashi, Yusuke |
| contents | 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 $a_i$-day interval. In this paper, we determine the optimal constant $α^* = 1.264\ldots {}$ such that every instance with $\sum_{i} \frac{1}{a_i} \ge α^*$ 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). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_06533 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Computer-Assisted Proof of the Optimal Density Bound for Pinwheel Covering Kawamura, Akitoshi Kobayashi, Yusuke Discrete Mathematics 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 $a_i$-day interval. In this paper, we determine the optimal constant $α^* = 1.264\ldots {}$ such that every instance with $\sum_{i} \frac{1}{a_i} \ge α^*$ 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). |
| title | A Computer-Assisted Proof of the Optimal Density Bound for Pinwheel Covering |
| topic | Discrete Mathematics |
| url | https://arxiv.org/abs/2510.06533 |