2020/04/24 by Martijn van Ee, van Ee, Martijn · 2 citations
Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #VLSI and FPGA Design Techniques
paper · pdf · doi:10.48550/arxiv.2004.11731
openalex publication_date 2020/04/24 · openalex created_date 2022/07/26 · openalex updated_date 2026/07/28
We study the discrete Bamboo Garden Trimming problem (BGT), where we are\ngiven n bamboos with different growth rates. At the end of each day, one can\ncut down one bamboo to height zero. The goal in BGT is to make a perpetual\nschedule of cuts such that the height of the tallest bamboo ever is minimized.\nHere, we improve the current best approximation guarantee by designing a\n12/7-approximation algorithm. This result is based on a reduction to the\nPinwheel Scheduling problem. We show that a guarantee of 12/7 is essentially\nthe best we can hope for if our algorithm is based on this type of reduction.\n