Document Open Access Logo

Cutting Bamboo down to Size

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

PDF
Thumbnail PDF

File

LIPIcs.FUN.2021.5.pdf
  • Filesize: 1.27 MB
  • 18 pages

Document Identifiers

Author Details

Davide Bilò
  • Department of Humanities and Social Sciences, University of Sassari, Italy
Luciano Gualà
  • Department of Enterprise Engineering, University of Rome "Tor Vergata", Italy
Stefano Leucci
  • Department of Information Engineering, Computer Science and Mathematics, University of L'Aquila, Italy
Guido Proietti
  • Department of Information Engineering, Computer Science and Mathematics, University of L'Aquila, Italy
  • Institute for System Analysis and Computer Science "Antonio Ruberti" (IASI CNR), Rome, Italy
Giacomo Scornavacca
  • Department of Humanities and Social Sciences, University of Sassari, Italy

Funding

  • Bilò, Davide: This work was partially supported by the Research Grant FBS2016_BILO, funded by "Fondazione di Sardegna" in 2016.
  • Scornavacca, Giacomo: This work was partially supported by Research Grant FBS2016_BILO, funded by "Fondazione di Sardegna" in 2016.

Acknowledgements

The authors would like to thank Francesca Marmigi for the picture of the robotic panda gardener in Figure 1. We are also grateful to an anonymous reviewer whose comments allowed us to significantly simplify the analysis of Reduce-Max.

Cite As Get BibTex

Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti, and Giacomo Scornavacca. Cutting Bamboo down to Size. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 5:1-5:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FUN.2021.5

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).

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • bamboo garden trimming
  • trimming oracles
  • approximation algorithms
  • pinwheel scheduling

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Micah Adler, Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, and Mike Paterson. A proportionate fair scheduling rule with good worst-case performance. In Arnold L. Rosenberg and Friedhelm Meyer auf der Heide, editors, SPAA 2003: Proceedings of the Fifteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, June 7-9, 2003, San Diego, California, USA (part of FCRC 2003), pages 101-108. ACM, 2003. URL: http://dx.doi.org/10.1145/777412.777430.
  2. Sultan S. Alshamrani, Dariusz R. Kowalski, and Leszek Antoni Gasieniec. Efficient discovery of malicious symptoms in clouds via monitoring virtual machines. In Yulei Wu, Geyong Min, Nektarios Georgalas, Jia Hu, Luigi Atzori, Xiaolong Jin, Stephen A. Jarvis, Lei (Chris) Liu, and Ramón Agüero Calvo, editors, 15th IEEE International Conference on Computer and Information Technology, CIT 2015; 14th IEEE International Conference on Ubiquitous Computing and Communications, IUCC 2015; 13th IEEE International Conference on Dependable, Autonomic and Secure Computing, DASC 2015; 13th IEEE International Conference on Pervasive Intelligence and Computing, PICom 2015, Liverpool, United Kingdom, October 26-28, 2015, pages 1703-1710. IEEE, 2015. URL: http://dx.doi.org/10.1109/CIT/IUCC/DASC/PICOM.2015.257.
  3. Michael A. Bender, Rathish Das, Martin Farach-Colton, Rob Johnson, and William Kuszmaul. Flushing without cascades. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 650-669. SIAM, 2020. URL: http://dx.doi.org/10.1137/1.9781611975994.40.
  4. Michael A. Bender, Martin Farach-Colton, and William Kuszmaul. Achieving optimal backlog in multi-processor cup games. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 1148-1157. ACM, 2019. URL: http://dx.doi.org/10.1145/3313276.3316342.
  5. Marijke H. L. Bodlaender, Cor A. J. Hurkens, Vincent J. J. Kusters, Frank Staals, Gerhard J. Woeginger, and Hans Zantema. Cinderella versus the wicked stepmother. In Jos C. M. Baeten, Thomas Ball, and Frank S. de Boer, editors, Theoretical Computer Science - 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012. Proceedings, volume 7604 of Lecture Notes in Computer Science, pages 57-71. Springer, 2012. URL: http://dx.doi.org/10.1007/978-3-642-33475-7_5.
  6. Gerth Stølting Brodal and Riko Jacob. Dynamic planar convex hull. In 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings, pages 617-626. IEEE Computer Society, 2002. URL: http://dx.doi.org/10.1109/SFCS.2002.1181985.
  7. Mee Yee Chan and Francis Y. L. Chin. General schedulers for the pinwheel problem based on double-integer reduction. IEEE Trans. Computers, 41(6):755-768, 1992. URL: http://dx.doi.org/10.1109/12.144627.
  8. Mee Yee Chan and Francis Y. L. Chin. Schedulers for larger classes of pinwheel instances. Algorithmica, 9(5):425-462, 1993. URL: http://dx.doi.org/10.1007/BF01187034.
  9. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  10. Mattia D'Emidio, Gabriele Di Stefano, and Alfredo Navarra. Bamboo garden trimming problem: Priority schedulings. Algorithms, 12(4):74, 2019. URL: http://dx.doi.org/10.3390/a12040074.
  11. Leszek Gasieniec, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas, Jie Min, and Tomasz Radzik. Bamboo garden trimming problem (perpetual maintenance of machines with different attendance urgency factors). In Bernhard Steffen, Christel Baier, Mark van den Brand, Johann Eder, Mike Hinchey, and Tiziana Margaria, editors, SOFSEM 2017: Theory and Practice of Computer Science - 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, January 16-20, 2017, Proceedings, volume 10139 of Lecture Notes in Computer Science, pages 229-240. Springer, 2017. URL: http://dx.doi.org/10.1007/978-3-319-51963-0_18.
  12. Michael H. Goldwasser. A survey of buffer management policies for packet switches. SIGACT News, 41(1):100-128, 2010. URL: http://dx.doi.org/10.1145/1753171.1753195.
  13. R. Holte, A. Mok, L. Rosier, I. Tulchinsky, and D. Varvel. The pinwheel: a real-time scheduling problem. In [1989] Proceedings of the Twenty-Second Annual Hawaii International Conference on System Sciences. Volume II: Software Track, volume 2, pages 693-702 vol.2, January 1989. URL: http://dx.doi.org/10.1109/HICSS.1989.48075.
  14. Robert Holte, Louis E. Rosier, Igor Tulchinsky, and Donald A. Varvel. Pinwheel scheduling with two distinct numbers. Theor. Comput. Sci., 100(1):105-135, 1992. URL: http://dx.doi.org/10.1016/0304-3975(92)90365-M.
  15. William Kuszmaul. Achieving optimal backlog in the vanilla multi-processor cup game. In Shuchi Chawla, editor, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 1558-1577. SIAM, 2020. URL: http://dx.doi.org/10.1137/1.9781611975994.96.
  16. Shun-Shii Lin and Kwei-Jay Lin. A pinwheel scheduler for three distinct numbers with a tight schedulability bound. Algorithmica, 19(4):411-426, 1997. URL: http://dx.doi.org/10.1007/PL00009181.
  17. Edward M. McCreight. Priority search trees. SIAM J. Comput., 14(2):257-276, 1985. URL: http://dx.doi.org/10.1137/0214021.
  18. Mark H. Overmars and Jan van Leeuwen. Maintenance of configurations in the plane. J. Comput. Syst. Sci., 23(2):166-204, 1981. URL: http://dx.doi.org/10.1016/0022-0000(81)90012-X.
  19. Theodore H. Romer and Louis E. Rosier. An algorithm reminiscent of euclidean-gcd computing a function related to pinwheel scheduling. Algorithmica, 17(1):1-10, 1997. URL: http://dx.doi.org/10.1007/BF02523234.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact