Bamboo Garden Trimming
You just bought a house by a lake. A bamboo garden grows outside the house and obstructs the beautiful view of the lake. To solve the problem, you also bought a robotic panda gardener which, once per day, can instantaneously trim a single bamboo. You have already measured the daily growth rate of every bamboo in the garden, and you are now faced with programming the gardener with a suitable perpetual schedule of bamboos to trim in order to keep the view as clear as possible.
The height of the tallest bamboo to ever appear in the garden is called the makespan. A compact data structure that can quickly report the next bamboo to cut in the schedule is called a Trimming Oracle. The goal is to design a Trimming Oracle that keeps the makespan as small as possible.
The following is a visualization of the Trimming Oracles presented in the paper Cutting Bamboo Down to Size that will appear in the proceedings of the 10th International Conference on Fun with Algorithms (FUN 2020).
- The Reduce-Max strategy always cuts the tallest bamboo, and the best known upper bound on the achieved makespan is 9H, where H is the total daily growth of the bamboo forest (i.e., the sum of the bamboo's growth rates).
- Reduce-Fastest(x) cuts the bamboo with the fastest growth rate among those of height at least xH and its makespan depends on the value of x>1. The choice of x that minimize the best known upper bound on the makespan is x = 1 + 1/sqrt(5) ≈ 1.45 and the corresponding makespan is (1 + φ)H < 2.62 H, where φ is the golden ratio.
- Tree is a novel trimming oracle that achieves a makespan of at most 2H.
Interactive simulation
Parsed input:
