# Bamboo Trimming Revisited: Simple Algorithms Can Do Well Too

**Authors:** John Kuszmaul  
**arXiv:** [2201.07350](https://arxiv.org/abs/2201.07350)  
**Date:** 2022-01-18  
**Summary page:** https://www.summarizepaper.com/fr/paper/2201.07350v2/

## Key points

- Le problème de la taille du bambou consiste à couper des bambous ayant des taux de croissance $h_1, h_2, \ldots, h_n$ satisfaisant $\sum_i h_i = 1$, afin de minimiser la hauteur du plus grand bambou (appelée arriéré).
- Il est étroitement lié à de nombreux problèmes d'ordonnancement et peut être considéré comme une variation du jeu de tasses à taux fixe.
- Des algorithmes sophistiqués en forme d'étoile atteignent l'arriéré optimal de 2 pour ce problème.
- L'algorithme Reduce-Max (qui coupe toujours le plus grand bambou) et l'algorithme Reduce-Fastest$(x)$ (qui coupe le bambou à croissance rapide parmi ceux qui ont une hauteur d'au moins $x$) atteignent un arriéré optimal de 2.
- L'arriéré optimal exact pour Reduce-Fastest$(x)$ est $x + 1$ pour tous les $x \ge 2$, et que Reduce-Fastest$(1)$ n’atteint pas un arriéré optimal de 2.
- Il existe un algorithme différent appelé stratégie axée sur les délais qui est très simple et atteint l'arrière optimal de 2.

## Summary

Le problème de la taille du bambou consiste à couper des bambous ayant des taux de croissance $h_1, h_2, \ldots, h_n$ satisfaisant $\sum_i h_i = 1$, afin de minimiser la hauteur du plus grand bambou (appelée arriéré). Il est étroitement lié à de nombreux problèmes d'ordonnancement et peut être considéré comme une variation du jeu de tasses à taux fixe. Des algorithmes sophistiqués en forme d'étoile atteignent l'arriéré optimal de 2 pour ce problème. Cependant, il restait une question ouverte quant à savoir s'il existait un algorithme simple avec la même garantie - des travaux récents ont montré que l'algorithme Reduce-Max (qui coupe toujours le plus grand bambou) et l'algorithme Reduce-Fastest$(x)$ (qui coupe le bambou à croissance rapide parmi ceux qui ont une hauteur d'au moins $x$) atteignent un arriéré optimal de 2. De plus, il a été démontré que l'arriéré optimal exact pour Reduce-Fastest$(x)$ est $x + 1$ pour tous les $x \ge 2$, et que Reduce-Fastest$(1)$ n’atteint pas un arriéré optimal de 2. Enfin, il existe un algorithme différent appelé stratégie axée sur les délais qui est très simple et atteint l'arrière optimal de 2.