|
|
||
|
IMADA -Department of Mathematics and Computer Science |
|
In the discrete bamboo garden trimming problem (BGT), first introduced by Gasieniec et al. at SOFSEM'17, we are given a set of $n$ bamboo that grow at rates $v_1,\ldots,v_n$ per day. We assume that these growth rates are arranged such that $v_1 \geq v_2 \geq \cdots \geq v_n$. Each day a robotic gardener cuts down one bamboo to height zero. The goal is to design a trimming schedule such that the height of the tallest bamboo that ever exists is minimized. Approximation algorithms for this problem were designed by reducing BGT to the pinwheel scheduling problem. In the pinwheel scheduling problem, we are given $n$ jobs with $($integer$)$ periods $p_1,\ldots,p_n$. Time is slotted, and only one job can be scheduled in each time slot. The goal is to design a schedule such that each job $i$ is scheduled at least once in any period of $p_i$ consecutive days, or to conclude that no such schedule exists. We improve on these results by using a more involved reduction and also give results for a continuous version of the problem, where the bamboo are positioned in some metric space and the gardener needs to travel between the bamboo to cut them. Host: Kim Skak Larsen SDU HOME | IMADA HOME Daniel Merkle |