TY - JOUR
T1 - Perpetual maintenance of machines with different urgency requirements
AU - Gasieniec, Leszek
AU - Jurdzinski, Tomasz
AU - Klasing, Ralf
AU - Levcopoulos, Christos
AU - Lingas, Andrzej
AU - Min, Jie
AU - Radzik, Tomasz
N1 - Funding Information:
L. Gąsieniec and J. Min's work was partially supported by Network Sciences and Technologies (NeST) at University of Liverpool. This study has been carried out in the frame of “the Investments for the future” Programme IdEx Bordeaux – SysNum (ANR-10-IDEX-03-02). R. Klasing's research was partially supported by the ANR project TEMPOGRAL (ANR-22-CE48-0001). C. Levcopoulos and A. Lingas work were supported by the Swedish Research Council grants 621-2017-03750 and 2018-04001. T. Radzik's work was supported in part by EPSRC grant EP/M005038/1, “Randomized algorithms for computer networks.” Part of this work was done while T. Radzik was visiting the LaBRI as a guest professor of the University of Bordeaux. T. Jurdzinski's work was supported by the Polish National Science Centre project no. 2020/39/B/ST6/03288. Preliminary versions of some of the results presented in this paper appeared in Proc. 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017), LNCS 10139, pp. 229–240, Springer (2017) [25].
Funding Information:
L. Gąsieniec and J. Min's work was partially supported by Network Sciences and Technologies (NeST) at University of Liverpool . This study has been carried out in the frame of “the Investments for the future” Programme IdEx Bordeaux – SysNum ( ANR - 10-IDEX-03-02 ). R. Klasing's research was partially supported by the ANR project TEMPOGRAL ( ANR-22-CE48-0001 ). C. Levcopoulos and A. Lingas work were supported by the Swedish Research Council grants 621-2017-03750 and 2018-04001 . T. Radzik's work was supported in part by EPSRC grant EP/M005038/1 , “Randomized algorithms for computer networks.” Part of this work was done while T. Radzik was visiting the LaBRI as a guest professor of the University of Bordeaux. T. Jurdzinski's work was supported by the Polish National Science Centre project no. 2020/39/B/ST6/03288 . Preliminary versions of some of the results presented in this paper appeared in Proc. 43rd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2017), LNCS 10139, pp. 229–240, Springer (2017) [25] .
Publisher Copyright:
© 2023 Elsevier Inc.
PY - 2024/2
Y1 - 2024/2
N2 - A garden is populated by n bamboos, each with its own daily growth rate. The Bamboo Garden Trimming Problem (BGT) is to design for a robotic gardener a perpetual schedule of cutting bamboos to keep the elevation of the garden as low as possible. The frequency of cutting is constrained by the time needed to move from one bamboo to the next, which is one day in Discrete BGT and is defined by the distance between the two bamboos in Continuous BGT. The bamboo garden is a metaphor for a collection of machines which have to be serviced, with different frequencies, by a robot which can service only one machine at a time. For Discrete BGT, we show tighter approximation algorithms, with one of them settling a long-standing conjecture about the related Pinwheel problem. For Continuous BGT, we propose approximation algorithms which achieve logarithmic approximation ratios.
AB - A garden is populated by n bamboos, each with its own daily growth rate. The Bamboo Garden Trimming Problem (BGT) is to design for a robotic gardener a perpetual schedule of cutting bamboos to keep the elevation of the garden as low as possible. The frequency of cutting is constrained by the time needed to move from one bamboo to the next, which is one day in Discrete BGT and is defined by the distance between the two bamboos in Continuous BGT. The bamboo garden is a metaphor for a collection of machines which have to be serviced, with different frequencies, by a robot which can service only one machine at a time. For Discrete BGT, we show tighter approximation algorithms, with one of them settling a long-standing conjecture about the related Pinwheel problem. For Continuous BGT, we propose approximation algorithms which achieve logarithmic approximation ratios.
UR - http://www.scopus.com/inward/record.url?scp=85170649660&partnerID=8YFLogxK
U2 - 10.1016/j.jcss.2023.103476
DO - 10.1016/j.jcss.2023.103476
M3 - Article
SN - 0022-0000
VL - 139
JO - JOURNAL OF COMPUTER AND SYSTEM SCIENCES
JF - JOURNAL OF COMPUTER AND SYSTEM SCIENCES
M1 - 103476
ER -