# Bamboo Garden Trimming Problem: Priority Schedulings +
## 3 Theoretical Results
### ReduceMax Scheduling  
In this section, the focus is on ReduceMax. The aim is to show that ReduceMax performs better than an \(O(\log n)\)-approximation algorithm. Actually, the approximation ratio is improved only for a specific set of input instances, by also exploiting some results achieved for priority schedulings. The results contained in this section constitute a path toward a partial achievement of the aim, leading to a 2-approximation ratio for ReduceMax when confined to some specific instances. By Fact 1, it en shown above that ReduceMax is a priority scheduling, regardless of the chosen threshold \(\tau\geq H\) required by Definition 4. It follows that ReduceMax inherits all results obtained in the previous section for priority schedulings. In particular, given an execution \(E\) obtained by applying ReduceMax, let \(l^{t}\) be the height of the bamboo cut in \(C_{t}\in L_{E}\), i.e., \(l^{t}=M(C_{t})\), and let \(\overline{M_{E}}=\frac{1}{\lambda_{E}}\sum\limits_{t=1}^{\lambda_{E}}l^{t}\) denote the average of the maximum heights reached by bamboos in \(L_{E}\). Then, for ReduceMax, Lemma 2 can be reformulated as follows. **Corollary 3** (On Average Height of Cuts of ReduceMax). : _Let \(E\) be an execution of ReduceMax. Then, \(\overline{M_{E}}\ =\ H\)._  
A natural intuitive property is provided in the next lemma. **Lemma 4** (On the Amounts of Cuts within a Cycle). : _Let \(E\) be an execution of ReduceMax. For any two indices \(i,j\in\{1,2,\ldots,n\}\) such that \(h_{i}\geq h_{j}\), it holds \(c_{i}\geq c_{j}\)._  
Proof. : By contradiction, assume that \(c_{i}<c_{j}\). Then, in cycle \(L_{E}\) there must be at least two cuts of \(b_{j}\) between two consecutive cuts of \(b_{i}\). However, since \(h_{i}\geq h_{j}\), \(b_{j}\) after the first cut will grow less than \(b_{i}\) and it will never reach \(b_{i}\) before its second cut, which is a contradiction. A direct consequence of Lemma 4 is that, if two bamboos exhibit the same growth rate, they also have the same number of cuts in the cycle. **Corollary 4** (Sufficient Condition for Same Number of Cuts). : _If \(E\) is an execution of ReduceMax, \(h_{i}=h_{j}\) implies \(c_{i}=c_{j}\)._  
Let \(m_{i}=\max\{m_{i}^{j}\ :\ j=1,2,\ldots,c_{i}\}\) be the maximum height reached by bamboo \(b_{i}\) in a cycle \(L_{E}\) of ReduceMax. The next result shows that \(c_{i}=1\) suffices to guarantee \(m_{i}<2H\). Basically, the next lemma guarantees that the approximation factor of ReduceMax reduces from \(O(\log n)\)[1] to 2 if all bamboos are cut only once within the cycle, i.e., when the cycle of ReduceMax is equivalent to the round-robin strategy. **Lemma 5** (Sufficient Condition for Bounded Maximum). : _Let \(E\) be an execution of ReduceMax. Then,_  
\[c_{i}=1\text{ for some }i\in\{1,2,\ldots,n\}\ \Longrightarrow\ m_{i}<2H.\]  
Proof. : First, notice that \(c_{i}=1\) suffices to immediately obtain \(m_{i}=\lambda_{E}\cdot h_{i}\). Moreover, by Corollary 3 it holds \(\overline{M_{E}}=H\), i.e., that \(\lambda_{E}\cdot H-\sum\limits_{t=1}^{\lambda_{E}}l^{t}=0\). Now, it is known that \(b_{i}\) is cut only once and, as \(L_{E}\) is periodic, \(C_{1}\) is equal to the configuration where the height of bamboo \(b_{i}\) is \(h_{i}\). Thus, each term \(l^{t}\) is trivially lower bounded by the height of bamboo \(b_{i}\) at day \(t\), i.e., \(l^{t}\geq t\cdot h_{i}\). Hence, \(\lambda_{E}\cdot H-\sum\limits_{t=1}^{\lambda_{E}}t\cdot h_{i}\geq 0\). Therefore, it holds that  
\[\lambda_{E}\cdot H\geq\sum\limits_{t=1}^{\lambda_{E}}t\cdot h_{i}\geq\frac{ \lambda_{E}\cdot(\lambda_{E}+1)}{2}\cdot h_{i}\]  
which implies  
\[\frac{\lambda_{E}^{2}}{2}\cdot h_{i}+\frac{\lambda_{E}}{2}\cdot h_{i}-\lambda_ {E}\cdot H\leq 0\]that is  
\[\lambda_{E}\cdot h_{i}+h_{i}-2\cdot H\leq 0.\]  
This in turn implies  
\[\lambda_{E}\cdot h_{i}<2H\]  
and hence \(m_{i}<2H\). If \(c_{i}=1\), for some \(i=1,2,\ldots n\), then similar to the proof of Lemma 5, a limit on the value of \(\lambda_{E}\) can be obtained, as summarised by the following corollary.