2025/08/25 by Mishra, Ahan, Rho, Parker, Kleinberg, Robert
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2508.18422
The density bound for schedulability for general pinwheel instances is (5)/(6), but density bounds better than (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 ( (1)/(m) ) and O ( (1)/(√(m)) ). We prove a density bound of 0.84 for m = 4, the first m for which a bound strictly better than (5)/(6) = 0.83 can be proven. In doing so, we develop new techniques, particularly a fast heuristic-based pinwheel solver and an unfolding operation.