Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Perpetual maintenance of machines with different urgency requirements

Gasieniec, Leszek ; Jurdziński, Tomasz ; Klasing, Ralf ; Levcopoulos, Christos LU orcid ; Lingas, Andrzej LU ; Min, Jie and Radzik, Tomasz (2024) In Journal of Computer and System Sciences 139.
Abstract
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 constraint 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... (More)
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 constraint 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. (Less)
Please use this url to cite or link to this publication:
author
; ; ; ; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
in
Journal of Computer and System Sciences
volume
139
article number
103476
publisher
Elsevier
external identifiers
  • scopus:85170649660
ISSN
0022-0000
DOI
10.1016/j.jcss.2023.103476
language
English
LU publication?
yes
id
dcec6d5b-a860-4ec4-8148-58ae7c98aa69
date added to LUP
2023-08-30 07:19:27
date last changed
2023-10-26 15:01:45
@article{dcec6d5b-a860-4ec4-8148-58ae7c98aa69,
  abstract     = {{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 constraint 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.}},
  author       = {{Gasieniec, Leszek and Jurdziński, Tomasz and Klasing, Ralf and Levcopoulos, Christos and Lingas, Andrzej and Min, Jie and Radzik, Tomasz}},
  issn         = {{0022-0000}},
  language     = {{eng}},
  publisher    = {{Elsevier}},
  series       = {{Journal of Computer and System Sciences}},
  title        = {{Perpetual maintenance of machines with different urgency requirements}},
  url          = {{http://dx.doi.org/10.1016/j.jcss.2023.103476}},
  doi          = {{10.1016/j.jcss.2023.103476}},
  volume       = {{139}},
  year         = {{2024}},
}