Felix Höhne

dblp:254/9651 · DBLP profile ↗
← Back
3ranked-venue papers
3as first author
3since 2021 · last 2023
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 3 first-author · 3 since 2021
YearPublicationVenuePosition
2023 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 v1, . . ., vn 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.
Felix Höhne, Rob van Stee
APPROX/RANDOM1
2021 Allocating contiguous blocks of indivisible chores fairly
Felix Höhne, Rob van Stee
Inf. Comput.1
2021 Buffer minimization with conflicts on a line
Felix Höhne, Rob van Stee
Theor. Comput. Sci.1