论文标题
竹制花园修剪问题的增强风车算法
An enhanced pinwheel algorithm for the bamboo garden trimming problem
论文作者
论文摘要
在竹制花园修剪问题（BGT）中，有一个由N BAMBOOS B（1），B（2），...，B（N）$的花园，每日增长率H（1）> = H（2）> = ...> ...> ...> ...> = H（N）。我们假设竹子的初始高度为零。园丁负责竹子，并根据某些时间表将其修剪为零。目的是设计一个永久的修剪时间表，以使竹制花园的高度尽可能低。我们考虑了所谓的离散BGT变体，允许园丁在每天结束时仅修剪一根竹子。对于离散的BGT，当前的最新近似算法利用了BGT与经典风车调度问题之间的关系，并提供了一个保证2个应用比率的解决方案。我们提出了一种替代风车调度算法，当总和h（j）>> h（1）时，近似值比收敛至12/7。另外，我们表明，所提出算法的近似值永远不会超过32000/16947约1.888。这是第一个达到比率严格较低比19/10的算法。
In the Bamboo Garden Trimming Problem (BGT), there is a garden populated by n bamboos b(1), b(2), ... , b(n)$ with daily growth rates h(1) >= h(2) >= ... >= h(n). We assume that the initial heights of bamboos are zero. A gardener is in charge of the bamboos and trims them to height zero according to some schedule. The objective is to design a perpetual schedule of trimming so as to maintain the height of the bamboo garden as low as possible. We consider the so-called discrete BGT variant, where the gardener is allowed to trim only one bamboo at the end of each day. For discrete BGT, the current state-of-the-art approximation algorithm exploits the relationship between BGT and the classical Pinwheel scheduling problem and provides a solution that guarantees a 2-approximation ratio. We propose an alternative Pinwheel scheduling algorithm with approximation ratio converging to 12/7 when sum h(j) > > h(1). Also, we show that the approximation ratio of the proposed algorithm never exceeds 32000/16947 approximately 1.888. This is the first algorithm reaching a ratio strictly inferior to 19/10.
