Journal
JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Volume 139, Issue -, Pages -Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.jcss.2023.103476
Keywords
Bamboo Garden Trimming Problem; BGT problem; Perpetual scheduling; Periodic maintenance; Pinwheel scheduling; Approximation algorithms; Patrolling
Ask authors/readers for more resources
This passage describes the Bamboo Garden Trimming Problem and presents approximation algorithms for both Discrete BGT and Continuous BGT.
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 Con-tinuous 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 set-tling a long-standing conjecture about the related Pinwheel problem. For Continuous BGT, we propose approximation algorithms which achieve logarithmic approximation ratios.(c) 2023 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available