2026-07-24T03:29:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18841 2024-03-06T11:02:42Z ddc:004 open_access

A 10/7-Approximation for Discrete Bamboo Garden Trimming and Continuous Trimming on Star Graphs Höhne, Felix van Stee, Rob bamboo garden trimming approximation algorithms scheduling 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Felix Höhne and Rob van Stee 2023 Is Part Of LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2023.16 urn:nbn:de:0030-drops-188417 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.16 eng https://creativecommons.org/licenses/by/4.0/legalcode