License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FUN.2021.5
URN: urn:nbn:de:0030-drops-127663
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12766/
Go to the corresponding LIPIcs Volume Portal

Bilò, Davide ; Gualà, Luciano ; Leucci, Stefano ; Proietti, Guido ; Scornavacca, Giacomo

Cutting Bamboo down to Size

pdf-format:
LIPIcs-FUN-2021-5.pdf (1 MB)

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 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 makespan, i.e., the maximum height ever reached by a bamboo.
Two natural strategies are Reduce-Max and Reduce-Fastest(x). Reduce-Max trims the tallest bamboo of the day, while Reduce-Fastest(x) trims the fastest growing bamboo among the ones that are taller than x. It is known that Reduce-Max and Reduce-Fastest(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 Reduce-Max and improve the one for Reduce-Fastest(x) to (3+√5)/2 < 2.62 for x = 1+1/√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 quickly determine the next bamboo to cut while requiring at most linear space. We formalize this aspect as the problem of designing a Trimming Oracle data structure, and we provide three efficient Trimming Oracles implementing different perpetual schedules, including those produced by Reduce-Max and Reduce-Fastest(x).

BibTeX - Entry

@InProceedings{bil_et_al:LIPIcs:2020:12766,
  author =	{Davide Bil{\`o} and Luciano Gual{\`a} and Stefano Leucci and Guido Proietti and Giacomo Scornavacca},
  title =	{{Cutting Bamboo down to Size}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{5:1--5:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Martin Farach-Colton and Giuseppe Prencipe and Ryuhei Uehara},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12766},
  URN =		{urn:nbn:de:0030-drops-127663},
  doi =		{10.4230/LIPIcs.FUN.2021.5},
  annote =	{Keywords: bamboo garden trimming, trimming oracles, approximation algorithms, pinwheel scheduling}
}

Keywords: bamboo garden trimming, trimming oracles, approximation algorithms, pinwheel scheduling
Collection: 10th International Conference on Fun with Algorithms (FUN 2021)
Issue Date: 2020
Date of publication: 16.09.2020
Supplementary Material: An interactive implementation of the Trimming Oracles described in this paper is available at https://www.isnphard.com/g/bamboo-garden-trimming/.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI