论文标题
重新审视的竹子修剪：简单的算法也可以做得很好
Bamboo Trimming Revisited: Simple Algorithms Can Do Well Too
论文作者
论文摘要
竹制修剪问题考虑了$ n $ bamboo的增长率$ h_1，h_2，\ ldots，h_n $满足$ \ sum_i h_i = 1 $。在给定的时间单位期间，每个竹子都会生长$ h_i $，然后竹制算法将其中一种竹子缩小到零高度。目的是最大程度地减少最高竹子的高度，也称为积压。竹制修剪问题与许多调度问题密切相关，可以看作是广泛研究的固定利率杯游戏的变体，但具有恒定的因素资源增强。 过去的工作给出了精致的风车算法，这些算法实现了竹制修剪问题中2的最佳积压。但是，这仍然是一个空旷的问题，是否存在具有相同保证的简单算法 - 最近的工作已专门用于回答这个问题的理论和实验努力。尤其是两种算法是自然候选者：减少最大算法（总是剪裁最高的竹子）和最快的$（x）$（x）$算法（从至少$ x $的高度中切掉了最快的竹子）。两种算法都猜想以达到积压2。 本文改善了最速度和最大最大速度的边界。 Among other results, we show that the exact optimal backlog for Reduce-Fastest$(x)$ is $x + 1$ for all $x \ge 2$ (proving a conjecture of D'Emidio, Di Stefano, and Navarra in the case of $x = 2$), and we show that Reduce-Fastest$(1)$ does not achieve backlog 2 (disproving a conjecture of D'Emidio, Di Stefano,和纳瓦拉）。 最后，我们表明有一种不同的算法，我们称之为截止日期驱动的策略，这既非常简单又实现了2的最佳积压。这解决了一个问题，即是否存在一种简单的最差最佳算法，以解决竹制剪裁问题。
The bamboo trimming problem considers $n$ bamboo with growth rates $h_1, h_2, \ldots, h_n$ satisfying $\sum_i h_i = 1$. During a given unit of time, each bamboo grows by $h_i$, and then the bamboo-trimming algorithm gets to trim one of the bamboo back down to height zero. The goal is to minimize the height of the tallest bamboo, also known as the backlog. The bamboo trimming problem is closely related to many scheduling problems, and can be viewed as a variation of the widely-studied fixed-rate cup game, but with constant-factor resource augmentation. Past work has given sophisticated pinwheel algorithms that achieve the optimal backlog of 2 in the bamboo trimming problem. It remained an open question, however, whether there exists a simple algorithm with the same guarantee -- recent work has devoted considerable theoretical and experimental effort to answering this question. Two algorithms, in particular, have appeared as natural candidates: the Reduce-Max algorithm (which always cuts the tallest bamboo) and the Reduce-Fastest$(x)$ algorithm (which cuts the fastest-growing bamboo out of those that have height at least $x$). Both algorithms are conjectured to achieve backlog 2. This paper improves the bounds for both Reduce-Fastest and Reduce-Max. Among other results, we show that the exact optimal backlog for Reduce-Fastest$(x)$ is $x + 1$ for all $x \ge 2$ (proving a conjecture of D'Emidio, Di Stefano, and Navarra in the case of $x = 2$), and we show that Reduce-Fastest$(1)$ does not achieve backlog 2 (disproving a conjecture of D'Emidio, Di Stefano, and Navarra). Finally, we show that there is a different algorithm, which we call the Deadline-Driven Strategy, that is both very simple and achieves the optimal backlog of 2. This resolves the question as to whether there exists a simple worst-case optimal algorithm for the bamboo trimming problem.
