论文标题
离散的竹制花园修剪问题的12/7- approximation算法
A 12/7-approximation algorithm for the discrete Bamboo Garden Trimming problem
论文作者
论文摘要
我们研究离散的竹制花园修剪问题（BGT），在该问题中，我们得到了n个竹子的增长率不同。每天结束时，一个人可以将一个竹子切成零。 BGT的目标是制定一个永久的切割时间表，以使有史以来最高的竹子的高度最小化。在这里，我们通过设计12/7-抗性算法来改善当前最佳近似保证。此结果是基于对风车调度问题的减少。我们表明，如果我们的算法基于这种减少，则可以保证12/7实质上是我们希望的最好的。
We study the discrete Bamboo Garden Trimming problem (BGT), where we are given n bamboos with different growth rates. At the end of each day, one can cut down one bamboo to height zero. The goal in BGT is to make a perpetual schedule of cuts such that the height of the tallest bamboo ever is minimized. Here, we improve the current best approximation guarantee by designing a 12/7-approximation algorithm. This result is based on a reduction to the Pinwheel Scheduling problem. We show that a guarantee of 12/7 is essentially the best we can hope for if our algorithm is based on this type of reduction.
