# Bamboo Garden Trimming Problem: Priority Schedulings +
## 4 Experimental Results  
In what follows, an extensive experimental evaluation of four priority scheduling strategies is provided. As already pointed out, a requirement for the scheduling strategies is to be fully deterministic. Hence, in the case of ties, that is when two or more bamboos are eligible to be cut with respect to the considered strategy, the bamboo having the biggest index is selected. The considered strategies are:ReduceMax (RMax, for short): This is the heuristic which performance is the most relevant to the experiments. In particular, in [1], based on [27], a \(O(\log n)\)-approximation guarantee has been established. However, the interest is in determining whether such a bound is tight in practice, i.e., whether the logarithmic factor is an accurate estimation. The strategy works in a greedy fashion by cutting each day the tallest bamboo.
* ReduceFastest\({}_{2}\) (RFast\({}_{2}\), for short): This is another greedy strategy introduced in [1]. It guarantees 4-approximation. However, this method requires ordering the input configurations according to the non-increasing order of the bamboos' growth rates. In fact, each day it cuts the fastest growing bamboo (the one having the biggest \(h_{i}\)) among those whose height exceeds threshold \(2H\). If none of the bamboos is taller than \(2H\), no cuts are performed.
* ReduceFastest\({}_{1}\) (RFast\({}_{1}\), for short): This is a variant of RFast\({}_{2}\), introduced here for the first time, obtained by decreasing the threshold from \(2H\) to \(H\), and by allowing the cut of the fastest growing bamboo also below the threshold. Basically, if none of the bamboos has reached height \(H\), the fastest growing bamboo is cut. This is a natural extension of RFast\({}_{2}\), and the aim of defining it is to check whether there are chances to obtain better performance with respect to RFast\({}_{2}\) and RMax. Note that RFast\({}_{1}\) is an ordered \(H\)-priority scheduling.
* ReduceMin (RMin, for short): This priority algorithm cuts each day the shortest bamboo, giving priorities to those above \(H\). The aim of defining this strategy is to evaluate performance of counter-intuitive methods, i.e., to see whether even in an adversarial approach one may obtain acceptable performances. RMin is a \(H\)-priority scheduling.  
To evaluate the behaviour of the scheduling strategies, all above mentioned scheduling algorithms have been implemented in C++. Moreover, it has been implemented a simulation framework for both generating input instances of the problem and measuring the performance, with respect to different metrics of interest, of the approaches on said instances. Different types of experiments have been performed, with varying values of \(n\) and \(H\) and different distribution of growth rates, which are described in the following sections.  
All sources were compiled with GNU g++ version 7.3.0 (O3 optimisation level) under Ubuntu Linux (Kernel 4.15.0-38). All testswere executed on a workstation equipped with an Intel\(\copyright\)Xeon\(\copyright\)CPU E5-2643 v33.40 GHz CPU and 128 GB of RAM.  
Notice that, for a fair comparison with respect to [1], in the experiments, it was assumed that the heights of all bamboos are initially null, that is \(C^{0}=(0,0,\ldots,0)\). Moreover, as the experiments involved ordered priority schedulings (namely RFast\({}_{1}\) and RFast\({}_{2}\)), without loss of generality, ordered configurations were considered.