标题： 离散点巡逻的最优密度界限 显示英文标题

标题： An Optimal Density Bound for Discretized Point Patrolling

摘要： 针轮问题是一个实时调度问题，它要求给定$n$个任务，其周期为$a_i \in \mathbb{N}$，是否可以在每个时间单位内无限地安排这些任务，使得每个任务$i$在每个长度为$a_i$单位的区间内都被安排。 我们研究了这一覆盖设置下的相应打包问题版本，在文献中被风格化为离散点巡逻问题。 具体而言，给定$n$个任务，其周期为$a_i$，问题要求是否可以将每一天分配给一个任务，使得每个任务$i$在\textit{最多}每隔$a_i$天被安排一次。 在任何情况下，实例的密度定义为任务周期倒数的总和。 最近，在装箱设置中长期存在的$5/6$密度界限猜想得到了肯定解决。 解决意味着任何密度至少为$5/6$的实例都是可调度的。 在覆盖设置中提出了一个相应的猜想，并在近期的多项工作中多次被重新提出。 我们通过证明每个密度至少为$\sum_{i = 0}^{\infty} 1/(2^i + 1) \approx 1.264$的离散化点巡逻实例都是可调度的，从而积极地解决了这个猜想。这显著优于当前已知的密度界限 1.546，并且实际上是最佳的。我们还研究了竹园修剪问题，这是针轮问题的一个优化变体。具体来说，给定$n$个增长速率，其值为$h_i \in \mathbb{N}$，目标是使具有相应增长速率的竹园的最大高度最小化，在每一步时间中允许修剪一棵竹子至零高度。我们为此问题实现了一个高效的$9/7$-近似算法，优于当前已知的最佳近似因子$4/3$。 显示英文摘要

摘要： 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$.