An Optimal Density Bound for Discretized Point Patrolling
Abstract
The pinwheel problem is a real-time scheduling problem that asks, given $n$ tasks with periods $a_i \in \mathbb{N}$, whether it is possible to infinitely schedule the tasks, one per time unit, such that every task $i$ is scheduled in every interval of $a_i$ units. We study a corresponding version of this packing problem in the covering setting, stylized as the discretized point patrolling problem in the literature. Specifically, given $n$ tasks with periods $a_i$, the problem asks whether it is possible to assign each day to a task such that every task $i$ is scheduled at \textit{most} once every $a_i$ days. The density of an instance in either case is defined as the sum of the inverses of task periods. Recently, the long-standing $5/6$ density bound conjecture in the packing setting was resolved affirmatively. The resolution means any instance with density at least $5/6$ is schedulable. A corresponding conjecture was made in the covering setting and renewed multiple times in more recent work. We resolve this conjecture affirmatively by proving that every discretized point patrolling instance with density at least $\sum_{i = 0}^{\infty} 1/(2^i + 1) \approx 1.264$ is schedulable. This significantly improves upon the current best-known density bound of 1.546 and is, in fact, optimal. We also study the bamboo garden trimming problem, an optimization variant of the pinwheel problem. Specifically, given $n$ growth rates with values $h_i \in \mathbb{N}$, the objective is to minimize the maximum height of a bamboo garden with the corresponding growth rates, where we are allowed to trim one bamboo tree to height zero per time step. We achieve an efficient $9/7$-approximation algorithm for this problem, improving on the current best known approximation factor of $4/3$.