# Bamboo Garden Trimming Problem: Priority Schedulings +
## 3 Theoretical Results
### Priority Schedulings
**Corollary 1** (Existence of a Cycle). : _Given a \(\tau\)-priority scheduling \(\sigma_{\tau}\) and an input \(I\), there exist two days \(t\) and \(t^{\prime}\), where \(t<t^{\prime}\), \(C^{t}=C^{t^{\prime}}\), and \(C^{t},C^{t^{\prime}}\in E(I,\sigma_{\tau})\)._  
Proof. : The claim follows from Lemma 1, since the number of configurations having volume at most \(n\tau\) is finite. By the above corollary, it follows that any priority scheduling stabilises in a cycle, eventually. In fact, by Definition 1, a priority scheduling (which is an oblivious scheduling) computes the same trimming operation if the same configuration shows up again. It is worth reminding that, in the case of ties, the bamboo having the biggest index is cut. In this paper, the focus is on the properties of such cycles, as they represent the perpetual trimming process that have to be executed indefinitely. Hence, the trend will be to disregard configurations preceding \(L_{E}\) where, given an execution \(E\), \(L_{E}\) denotes its periodic part (i.e., the sequence of configurations in the cycle). In particular, to better characterise such cycles, the next notation is introduced:  
* \(L_{E}=(C_{1}=C^{t^{\prime}},C_{2}=C^{t^{\prime}+1},C_{3},\ldots,C_{\lambda_{E }})\), where \(C^{t^{\prime}}\) is the first configuration belonging to \(L_{E}\), reached from \(C^{0}\), and \(\lambda_{E}=|L_{E}|\) is the length of the cycle, i.e., the number of configurations in \(L_{E}\). * \(l^{t}\) is the height of the bamboo cut in \(C_{t}\in L_{E}\). It is assumed \(l^{t}=0\) if no bamboo is cut. * \(c_{i}\) is the number of times bamboo \(b_{i}\) is cut in \(L_{E}\), for each \(i=1,\ldots,n\), which is equal to the number of relative maximum heights reached by \(b_{i}\) in the cycle. * \(m_{i}^{j}\) is the relative maximum height reached by \(b_{i}\) in the cycle just before the \(j\)th cut, for \(i=1,\ldots,n\) and \(j=1,\ldots,c_{i}\). Note that, by definition, during day \(t\), \(l^{t}=m_{i}^{j}\) for some values of \(i\) and \(j\). * \(M_{i}=\sum\limits_{j=1}^{c_{i}}m_{i}^{j}\) is the sum of the relative maximum heights reached by \(b_{i}\). The next lemma provides a very useful property of the cuts that are performed within a cycle of a priority scheduling. In particular, it can be shown that the average value of heights reached by bamboos in \(L_{E}\), just before a cut, is always \(H\). As shown below, the lemma is exploited to prove that within some specific circumstances ReduceMax is a 2-approximation algorithm. **Lemma 2** (On Average Height of Cuts within a Cycle). : _Given an execution \(E\) of a priority scheduling, then \(\frac{1}{\lambda_{E}}\sum\limits_{t=1}^{\lambda_{E}}l^{t}=H\)._  
Proof. : Let \(\Delta_{V}^{t}=V(C_{t})-V(C_{t-1})\) be the change of the volume from \(C_{t-1}\) to \(C_{t}\), for any \(t=1,\ldots\lambda_{E}\). \(C_{0}\equiv C_{\lambda_{E}}\), since cycle \(L_{E}\) exists by Corollary 1. Thus, it holds \(\Delta_{V}^{t}=H-l^{t}\), because at day \(t\) the bamboo of height \(l^{t}\) is cut and all bamboos grow by \(H\) in total. Now, since \(\sum\limits_{t=1}^{\lambda_{E}}\Delta_{V}^{t}\) must be equal to zero, as configurations in \(L_{E}\) come periodically, then:  
\[\sum\limits_{t=1}^{\lambda_{E}}\Delta_{V}^{t}=\sum\limits_{t=1}^{\lambda_{E}}( H-l^{t})=\lambda_{E}\cdot H-\sum\limits_{t=1}^{\lambda_{E}}l^{t}=0.\]  
Therefore, it is obtained that  
\[\sum\limits_{t=1}^{\lambda_{E}}l^{t}=\lambda_{E}\cdot H\]  
and the claim holds. The next lemma as well as the subsequent corollary are not exploited in the rest of the paper as the focus is on analysing the performance of ReduceMax. However, such results constitute interesting and elegant properties characterising general priority schedulings, hence they are worth being reported. In particular, in what follows, the length of \(L_{E}\) is characterised in terms of the maximum height reached by any bamboo having growth rate equal to \(h_{i}\). **Lemma 3** (Characterisation of \(\lambda_{E}\)).