论文标题
将竹子切成大小
Cutting Bamboo Down to Size
论文作者
论文摘要
本文研究了编程机器人熊猫园丁的问题，以防止竹制花园阻碍您房屋的湖景。 花园由$ n $竹茎组成，并以已知的每日增长率，园丁每天最多可以切入一根竹子。作为计算机科学家，您发现这个问题已经在[GąSieniec等人，Sofsem'17]中正式化为竹制花园修剪（BGT）问题，在该问题中，目标是计算永久时间表的目标（即，即班鲍斯（I. 两种自然策略是减少最大策略，并减少速度（x）。减少最高的竹子，减少最高的竹子，而最快的（x）将生长最快的竹子修剪为高于$ x $的竹子。众所周知，减少最大最佳（x）的最佳选择分别为$ o（\ log n）$和$ 4 $，分别为$ x = 2 $。我们证明了第一个常数上限为$ 9 $的$ 9 $，并改善了降低 - 速度（x）至$ \ frac {3+ \ sqrt {5}}} {2} {2} <2.62 $ for $ x = 1+\ frac {1+\ frac {1} {\ sqrt {5}} $。 另一个关键方面源于您的机器人园丁的处理能力和记忆力有限。然后，对于算法而言，能够快速确定在最大线性空间时要切割的下一个竹子。我们将此方面形式化为设计修剪的甲骨文数据结构的问题，我们提供了三个有效的修剪甲骨文，以实施不同的永久时间表，包括降低 - 最大速度和降低 - 速度（x）产生的时间表。
This paper studies the problem of programming a robotic panda gardener to keep a bamboo garden from obstructing the view of the lake by your house. The garden consists of $n$ bamboo stalks with known daily growth rates and the gardener can cut at most one bamboo per day. As a computer scientist, you found out that this problem has already been formalized in [Gąsieniec et al., SOFSEM'17] as the Bamboo Garden Trimming (BGT) problem, where the goal is that of computing a perpetual schedule (i.e., the sequence of bamboos to cut) for the robotic gardener to follow in order to minimize the makespan, i.e., the maximum height ever reached by a bamboo. Two natural strategies are Reduce-Max and Reduce-Fastest(x). Reduce-Max trims the tallest bamboo of the day, while Reduce-Fastest(x) trims the fastest growing bamboo among the ones that are taller than $x$. It is known that Reduce-Max and Reduce-Fastest(x) achieve a makespan of $O(\log n)$ and $4$ for the best choice of $x=2$, respectively. We prove the first constant upper bound of $9$ for Reduce-Max and improve the one for Reduce-Fastest(x) to $\frac{3+\sqrt{5}}{2} < 2.62$ for $x=1+\frac{1}{\sqrt{5}}$. Another critical aspect stems from the fact that your robotic gardener has a limited amount of processing power and memory. It is then important for the algorithm to be able to quickly determine the next bamboo to cut while requiring at most linear space. We formalize this aspect as the problem of designing a Trimming Oracle data structure, and we provide three efficient Trimming Oracles implementing different perpetual schedules, including those produced by Reduce-Max and Reduce-Fastest(x).
