{"ID":2878722,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2508.18422","arxiv_id":"2508.18422","title":"Improving Pinwheel Density Bounds for Small Minimums","abstract":"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.","short_abstract":"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 l...","url_abs":"https://arxiv.org/abs/2508.18422","url_pdf":"https://arxiv.org/pdf/2508.18422v1","authors":"[\"Ahan Mishra\",\"Parker Rho\",\"Robert Kleinberg\"]","published":"2025-08-25T19:11:16Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}