# Bamboo Garden Trimming Problem: Priority Schedulings +
## 1 Introduction
### Related Work  
The BGT problem, while of independent combinatorial interest, originates from perpetual testing of virtual machines in cloud systems [4]. In such systems, the frequency in which virtual machines are tested for undesirable symptoms varies depending on the importance of dedicated cloud operational mechanisms. The BGT problem considered here is also a close relative of several classical algorithmic problems which focus on _monitoring_ including _Graph Exploration_[5; 6; 7; 8], _Art Gallery Problem_[9] and its dynamic extension \(k\)_-Watchmen Problem_[10]. In the work on _Patrolling_[11; 12], the studies focus on monitoring a set of points with the same frequency of attendance, whereas in [13], the frequency may vary.  
In this paper, similarly to [1], the focus is on the case where each bamboo has its own attendance factor, which makes it related to _periodic scheduling_[14], several variants of _Pinwheel_ related problems [2; 15; 16; 17] including _periodic Pinwheel_ problem [18; 19] and _Pinwheel scheduling_[20], as well as the concept of _P-fairness_ in sharing multiple copies of some resource among various tasks [21; 22]. It is worth pointing out here that the intractability of BGT results from the hardness of Pinwheel scheduling proved in [23].  
Of course, the relevance of a new variant of scheduling is of main interest to the algorithmic community as scheduling issues represent fundamental primitives in many contexts. To this respect, it is worth citinib the close relation of the proposed BGT problem with the work done on similar settings in [24; 25]. The main difference basically resides in the objective function. In fact, in [24; 25], the aim is to minimise the long-run average height of the bamboos, whereas in BGT the aim concerns the minimisation of the maximum height ever reached by the bamboos.  
In related research on minimising the maximum occupancy of a buffer in a system of \(n\) buffers, the usual setting is a game between the player and the adversary [26; 27; 28]. The adversary decides how a fixed total increase of data in each round is distributed among the buffers and tries to maximise the maximum occupancy of a buffer. The player decides which buffer (or buffers) should be emptied next and tries to minimise the maximum buffer size. The upper bounds developed in this more general context can be translated into upper bounds for the BGT problem. However, here the aim is to derive tighter bounds for the case where the knowledge of growth rates is not exploited, hence adopting strategies able to deal with input data being either partially or entirely unknown.  
Probably the most natural algorithm to keep the elevation of the bamboo garden low is the greedy approach of always cutting the currently tallest bamboo. This method, which is agnostic with respect to growth rates, was first coined in [4] under the name of ReduceMax and further studied in [1]. This strategy was also considered independently (and under a different name) in the adversarial setting of buffer minimisation problems [27]. Another method studied in [1] is the ReduceFastest\({}_{2}\) approach, in which the fastest growing bamboo is cut but only among those having height above the threshold \(2H\), where  
\[H=\sum_{i=1}^{n}h_{i}.\]  
Value \(H\) represents the total daily growth of the system of bamboos and it is known [1] that one cannot keep bamboos below this threshold level. From [1], it is known that ReduceFastestprovides a constant approximation to BGT, i.e., none of the bamboos grows above height \(4H\). However, its applicability depends on the knowledge of value \(H\) and at least an ordering of the bamboos with respect to their growth rates. More interestingly, ReduceMax does not require such a knowledge but surprisingly it is not well understood. While there are insights that it should perform better than ReduceFastest\({}_{2}\), the only upper bound known for the maximum height of bamboos is \(O(H\cdot\log n)\)[1].