License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.16
URN: urn:nbn:de:0030-drops-188417
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18841/
Höhne, Felix ;
van Stee, Rob
A 10/7-Approximation for Discrete Bamboo Garden Trimming and Continuous Trimming on Star Graphs
Abstract
In the discrete bamboo garden trimming problem we are given n bamboo that grow at rates v_1,… ,v_n per day. Each day a robotic gardener cuts down one bamboo to height 0. The goal is to find a schedule that minimizes the height of the tallest bamboo that ever exists.
We present a 10/7-approximation algorithm that is based on a reduction to the pinwheel problem. This is consistent with the approach of earlier algorithms, but some new techniques are used that lead to a better approximation ratio.
We also consider the continuous version of the problem where the gardener travels in a metric space between plants and cuts down a plant each time he reaches one. We show that on the star graph the previously proposed algorithm Reduce-Fastest is a 6-approximation and the known Deadline-Driven Strategy is a (3+2√2)-approximation. The Deadline-Driven Strategy is also a (9+2√5)-approximation on star graphs with multiple plants on each branch.
BibTeX - Entry
@InProceedings{hohne_et_al:LIPIcs.APPROX/RANDOM.2023.16,
author = {H\"{o}hne, Felix and van Stee, Rob},
title = {{A 10/7-Approximation for Discrete Bamboo Garden Trimming and Continuous Trimming on Star Graphs}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
pages = {16:1--16:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-296-9},
ISSN = {1868-8969},
year = {2023},
volume = {275},
editor = {Megow, Nicole and Smith, Adam},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18841},
URN = {urn:nbn:de:0030-drops-188417},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.16},
annote = {Keywords: bamboo garden trimming, approximation algorithms, scheduling}
}
