{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T02:24:30Z","timestamp":1774751070054,"version":"3.50.1"},"reference-count":30,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2019,4,13]],"date-time":"2019-04-13T00:00:00Z","timestamp":1555113600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The paper deals with the Bamboo Garden Trimming (BGT) problem introduced in [G\u0105sieniec et al., SOFSEM\u201917]. The problem is difficult to solved due to its close relationship to Pinwheel scheduling. The garden with n bamboos is an analogue of a system of n machines that have to be attended (e.g., serviced) with different frequencies. During each day, bamboo     b i     grows an extra height      h i  ,     for     i = 1 , \u2026 , n     and, on the conclusion of the day, at most one bamboo has its entire height cut.The goal is to design a perpetual schedule of cuts to keep the height of the tallest ever bamboo as low as possible. The contribution in this paper is twofold, and is both theoretical and experimental. In particular, the focus is on understanding what has been called priority schedulings, i.e., cutting strategies where priority is given to bamboos whose current height is above a threshold greater than or equal to     H =  \u2211  i = 1  n   h i     . Value H represents the total daily growth of the system and it is known that one cannot keep bamboos in the garden below this threshold indefinitely. As the first result, it is proved that, for any distribution of integer growth rates      h 1  , \u2026 ,  h n      and any priority scheduling, the system stabilises in a fixed cycle of cuts. Then, the focus is on the so-called     ReduceMax     strategy, a greedy priority scheduling that each day cuts the tallest bamboo, regardless of the growth rates distribution.     ReduceMax     is known to provide a     O ( log n )    -approximation, with respect to the lower bound H. One of the main results achieved is that, if     ReduceMax     stabilises in a round-robin type cycle, then it guarantees 2-approximation. Furthermore, preliminary results are provided relating the structure of the input instance, in terms of growth rates, and the behavior of     ReduceMax     when applied to such inputs. Finally, a conjecture that     ReduceMax     is 2-approximating for the BGT problem is claimed, hence an extended experimental evaluation was conducted to support the conjecture and to compare     ReduceMax     with other relevant scheduling algorithms. The obtained results show that     ReduceMax    : (i) provides 2-approximation in all considered inputs; and (ii) always outperforms other considered strategies, even those for which better worst case approximation guarantees have been proven.<\/jats:p>","DOI":"10.3390\/a12040074","type":"journal-article","created":{"date-parts":[[2019,4,15]],"date-time":"2019-04-15T11:15:58Z","timestamp":1555326958000},"page":"74","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Bamboo Garden Trimming Problem: Priority Schedulings"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7833-9520","authenticated-orcid":false,"given":"Mattia","family":"D\u2019Emidio","sequence":"first","affiliation":[{"name":"Department of Information Engineering, Computer Science and Mathematics, University of L\u2019Aquila; 67100 L\u2019Aquila, Italy"}]},{"given":"Gabriele","family":"Di Stefano","sequence":"additional","affiliation":[{"name":"Department of Information Engineering, Computer Science and Mathematics, University of L\u2019Aquila; 67100 L\u2019Aquila, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8547-5934","authenticated-orcid":false,"given":"Alfredo","family":"Navarra","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Computer Science, University of Perugia, 06123 Perugia, Italy"}]}],"member":"1968","published-online":{"date-parts":[[2019,4,13]]},"reference":[{"key":"ref_1","first-page":"229","article-title":"Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors)","volume":"Volume 10139","author":"Klasing","year":"2017","journal-title":"SOFSEM 2017: Theory and Practice of Computer Science, Proceedings of the 43rd International Conference on Current Trends in Theory and Practice of Computer Science, Limerick, Ireland, 16\u201320 January 2017"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Holte, R., Mok, A., Rosier, L., Tulchinsky, I., and Varvel, D. (1989, January 3\u20136). The pinwheel: A real-time scheduling problem. Proceedings of the 22nd Annual Hawaii International Conference on System Sciences, Kailua-Kona, HI, USA.","DOI":"10.1109\/HICSS.1989.48075"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1007\/s00453-002-0938-9","article-title":"Pinwheel Scheduling: Achievable Densities","volume":"34","author":"Fishburn","year":"2002","journal-title":"Algorithmica"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Alshamrani, S., Kowalski, D.R., and G\u0105sieniec, L. (2015, January 26\u201329). How Reduce Max Algorithm Behaves with Symptoms Appearance on Virtual Machines in Clouds. Proceedings of the 2015 International Conference on Cloud Computing (ICCC), Riyadh, Saudi Arabia.","DOI":"10.1109\/CLOUDCOMP.2015.7149641"},{"key":"ref_5","first-page":"802","article-title":"Fast periodic graph exploration with constant memory","volume":"74","author":"Klasing","year":"2008","journal-title":"J. Comput. Syst. Sci."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1007\/s00453-011-9518-1","article-title":"Graph Decomposition for Memoryless Periodic Exploration","volume":"63","author":"Kosowski","year":"2012","journal-title":"Algorithmica"},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/j.ic.2018.09.010","article-title":"Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane","volume":"263","author":"Frigioni","year":"2018","journal-title":"Inf. Comput"},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/j.tcs.2015.09.002","article-title":"Explore and repair graphs with black holes using mobile entities","volume":"605","author":"Frigioni","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1016\/0020-0190(86)90050-5","article-title":"On gallery watchmen in grids","volume":"23","author":"Ntafos","year":"1986","journal-title":"Inf. Process. Lett."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Urrutia, J. (2000). Art gallery and illumination problems. Handbook of Computational Geometry, Elsevier.","DOI":"10.1016\/B978-044482537-7\/50023-1"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Collins, A., Czyzowicz, J., G\u0105sieniec, L., Kosowski, A., Kranakis, E., Krizanc, D., Martin, R., and Morales Ponce, O. (2013, January 23\u201325). Optimal Patrolling of Fragmented Boundaries. Proceedings of the 25th Annual ACM Symposium on Parallelism in Algorithms and Architectures, Montr\u00e9al, QC, Canada.","DOI":"10.1145\/2486159.2486176"},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1007\/978-3-642-23719-5_59","article-title":"Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds","volume":"Volume 6942","author":"Czyzowicz","year":"2011","journal-title":"Algorithms\u2014ESA 2011, Proceedings of the 19th Annual European Symposium, Saarbr\u00fccken, Germany, 5\u20139 September 2011"},{"key":"ref_13","first-page":"367","article-title":"Patrolling a Path Connecting a Set of Points with Unbalanced Frequencies of Visits","volume":"Volume 10706","author":"Chuangpishit","year":"2018","journal-title":"SOFSEM 2018: Theory and Practice of Computer Science, Proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science, Krems, Austria, 29 January\u20132 February 2018"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"550","DOI":"10.1137\/0402049","article-title":"A Mathematical Model for Periodic Scheduling Problems","volume":"2","author":"Serafini","year":"1989","journal-title":"SIAM J. Discret. Math."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"755","DOI":"10.1109\/12.144627","article-title":"General schedulers for the pinwheel problem based on double-integer reduction","volume":"41","author":"Chan","year":"1992","journal-title":"IEEE Trans. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1007\/BF01187034","article-title":"Schedulers for larger classes of pinwheel instances","volume":"9","author":"Chan","year":"1993","journal-title":"Algorithmica"},{"key":"ref_17","unstructured":"Hsueh, C., and Lin, K. (1996, January 4\u20136). An Optimal Pinwheel Scheduler Using the Single-number Reduction Technique. Proceedings of the 17th IEEE Real-Time Systems Symposium, Washington, DC, USA."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0304-3975(92)90365-M","article-title":"Pinwheel scheduling with two distinct numbers","volume":"100","author":"Holte","year":"1992","journal-title":"Theor. Comput. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/PL00009181","article-title":"A Pinwheel Scheduler for Three Distinct Numbers with a Tight Schedulability Bound","volume":"19","author":"Lin","year":"1997","journal-title":"Algorithmica"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02523234","article-title":"An algorithm reminiscent of euclidean-gcd for computing a function related to pinwheel scheduling","volume":"17","author":"Romer","year":"1997","journal-title":"Algorithmica"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1109\/12.709381","article-title":"Pfair scheduling of generalized pinwheel task systems","volume":"47","author":"Baruah","year":"1998","journal-title":"IEEE Trans. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"600","DOI":"10.1007\/BF01940883","article-title":"Proportionate progress: A notion of fairness in resource allocation","volume":"15","author":"Baruah","year":"1996","journal-title":"Algorithmica"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1016\/0165-6074(89)90128-2","article-title":"Algorithms and complexity of the periodic maintenance problem","volume":"27","author":"Mok","year":"1989","journal-title":"Microprocess. Microprogram."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/S0166-218X(97)00119-4","article-title":"The scheduling of maintenance service","volume":"82","author":"Anily","year":"1998","journal-title":"Discret. Appl. Math."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1023\/A:1018971222185","article-title":"Scheduling maintenance services to three machines","volume":"86","author":"Anily","year":"1999","journal-title":"Ann. Oper. Res."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.tcs.2015.08.027","article-title":"The Minimum Backlog Problem","volume":"605","author":"Bender","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"ref_27","first-page":"57","article-title":"Cinderella versus the Wicked Stepmother","volume":"Volume 6942","author":"Bodlaender","year":"2012","journal-title":"TCS 2012: Theoretical Computer Science, Proceedings of the IFIP Theoretical Computer Science Conference, Amsterdam, The Netherlands, 26\u201328 September 2012"},{"key":"ref_28","first-page":"862","article-title":"The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts","volume":"Volume 2076","author":"Chrobak","year":"2001","journal-title":"Automata, Languages and Programming, Proceedings of the 28th International Colloquium on Automata, Languages, and Programming, Crete, Greece, 8\u201312 July 2001"},{"key":"ref_29","first-page":"136","article-title":"Priority Scheduling in the Bamboo Garden Trimming Problem","volume":"Volume 11376","author":"Navarra","year":"2019","journal-title":"SOFSEM 2019: Theory and Practice of Computer Science, Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science, Nov\u00fd Smokovec, Slovakia, 27\u201330 January 2019"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1112\/plms\/s2-17.1.75","article-title":"Asymptotic formulas in combinatorial analysis","volume":"17","author":"Hardy","year":"1918","journal-title":"Proc. Lond. Math. Soc."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/4\/74\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:45:18Z","timestamp":1760186718000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/12\/4\/74"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4,13]]},"references-count":30,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2019,4]]}},"alternative-id":["a12040074"],"URL":"https:\/\/doi.org\/10.3390\/a12040074","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4,13]]}}}