Improving Pinwheel Density Bounds for Small Minimums
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915462958284800 |
|---|---|
| author | Mishra, Ahan Rho, Parker Kleinberg, Robert |
| author_facet | Mishra, Ahan Rho, Parker Kleinberg, Robert |
| contents | The density bound for schedulability for general pinwheel instances is $\frac{5}{6}$, but density bounds better than $\frac{5}{6}$ can be shown for cases in which the minimum element $m$ of the instance is large. Several recent works have studied the question of the 'density gap' as a function of $m$, with best known lower and upper bounds of $O \left( \frac{1}{m} \right)$ and $O \left( \frac{1}{\sqrt{m}} \right)$. We prove a density bound of $0.84$ for $m = 4$, the first $m$ for which a bound strictly better than $\frac{5}{6} = 0.8\overline{3}$ can be proven. In doing so, we develop new techniques, particularly a fast heuristic-based pinwheel solver and an unfolding operation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_18422 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improving Pinwheel Density Bounds for Small Minimums Mishra, Ahan Rho, Parker Kleinberg, Robert Data Structures and Algorithms The density bound for schedulability for general pinwheel instances is $\frac{5}{6}$, but density bounds better than $\frac{5}{6}$ can be shown for cases in which the minimum element $m$ of the instance is large. Several recent works have studied the question of the 'density gap' as a function of $m$, with best known lower and upper bounds of $O \left( \frac{1}{m} \right)$ and $O \left( \frac{1}{\sqrt{m}} \right)$. We prove a density bound of $0.84$ for $m = 4$, the first $m$ for which a bound strictly better than $\frac{5}{6} = 0.8\overline{3}$ can be proven. In doing so, we develop new techniques, particularly a fast heuristic-based pinwheel solver and an unfolding operation. |
| title | Improving Pinwheel Density Bounds for Small Minimums |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.18422 |