This paper studies the problem of programming a robotic panda gardener to keep a bamboo garden from obstructing the view of the lake by your house. The garden consists of \$n\$ bamboo stalks with known daily growth rates and the gardener can cut at most one bamboo per day. As a computer scientist, you found out that this problem has already been formalized in [Gąsieniec et al., SOFSEM'17] as the emph{Bamboo Garden Trimming (BGT) problem}, where the goal is that of computing a perpetual schedule (i.e., the sequence of bamboos to cut) for the robotic gardener to follow in order to minimize the emph{makespan}, i.e., the maximum height ever reached by a bamboo. Two natural strategies are educemax and educefastest{x}. educemax trims the tallest bamboo of the day, while educefastest{x} trims the fastest growing bamboo among the ones that are taller than \$x\$. It is known that educemax and educefastest{x} achieve a makespan of \$O(log n)\$ and \$4\$ for the best choice of \$x=2\$, respectively. We prove the first constant upper bound of \$9\$ for educemax and improve the one for educefastest{x} to \$rac{3+sqrt{5}}{2} &lt; 2.62\$ for \$x=1+rac{1}{sqrt{5}}\$. Another critical aspect stems from the fact that your robotic gardener has a limited amount of processing power and memory. It is then important for the algorithm to be able to emph{quickly} determine the next bamboo to cut while requiring at most linear space. We formalize this aspect as the problem of designing a emph{Trimming Oracle} data structure, and we provide three efficient Trimming Oracles implementing different perpetual schedules, including those produced by educemax and educefastest{\$x\$}.

Davide, B., Guala', L., Stefano, L., Guido, P., & Giacomo, S. (2020). Cutting bamboo down to size. In Leibniz International Proceedings in Informatics, LIPIcs.

### Cutting bamboo down to size

#### Abstract

This paper studies the problem of programming a robotic panda gardener to keep a bamboo garden from obstructing the view of the lake by your house. The garden consists of \$n\$ bamboo stalks with known daily growth rates and the gardener can cut at most one bamboo per day. As a computer scientist, you found out that this problem has already been formalized in [Gąsieniec et al., SOFSEM'17] as the emph{Bamboo Garden Trimming (BGT) problem}, where the goal is that of computing a perpetual schedule (i.e., the sequence of bamboos to cut) for the robotic gardener to follow in order to minimize the emph{makespan}, i.e., the maximum height ever reached by a bamboo. Two natural strategies are educemax and educefastest{x}. educemax trims the tallest bamboo of the day, while educefastest{x} trims the fastest growing bamboo among the ones that are taller than \$x\$. It is known that educemax and educefastest{x} achieve a makespan of \$O(log n)\$ and \$4\$ for the best choice of \$x=2\$, respectively. We prove the first constant upper bound of \$9\$ for educemax and improve the one for educefastest{x} to \$rac{3+sqrt{5}}{2} < 2.62\$ for \$x=1+rac{1}{sqrt{5}}\$. Another critical aspect stems from the fact that your robotic gardener has a limited amount of processing power and memory. It is then important for the algorithm to be able to emph{quickly} determine the next bamboo to cut while requiring at most linear space. We formalize this aspect as the problem of designing a emph{Trimming Oracle} data structure, and we provide three efficient Trimming Oracles implementing different perpetual schedules, including those produced by educemax and educefastest{\$x\$}.
##### Scheda breve Scheda completa Scheda completa (DC)
The Tenth International Conference on Fun with Algorithms (FUN 2021)
Favignana, Italy
2021
10
Rilevanza internazionale
contributo
Settore INF/01
eng
Intervento a convegno
Davide, B., Guala', L., Stefano, L., Guido, P., & Giacomo, S. (2020). Cutting bamboo down to size. In Leibniz International Proceedings in Informatics, LIPIcs.
Davide, B; Guala', L; Stefano, L; Guido, P; Giacomo, S
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: `http://hdl.handle.net/2108/251795`
• ND
• 1
• ND