\begin{document}

\pagestyle{headings}

\title{Perpetual maintenance of machines with different urgency requirements
\thanks{
L.~G\k asieniec and J.~Min's work was partially supported by Network Sciences and Technologies (NeST)
at University of Liverpool.

This study has been carried out in the frame of ``the Investments for the future'' 
Programme IdEx Bordeaux -- SysNum (ANR-10-IDEX-03-02). 
T.~Radzik's work was supported in part by
EPSRC grant EP/M005038/1, ``Randomized algorithms for computer networks.''
Part of this work was done while T.~Radzik was visiting the LaBRI as a guest professor of the University of Bordeaux.
An extended abstract of this work appeared in Proc.~43rd International Conference on Current Trends in Theory 
and Practice of Computer Science (SOFSEM 2017), LNCS 10139, pp.~229--240, 
Springer (2017)~\cite{DBLP:conf/sofsem/GasieniecKLLMR17}.
} 

}

\author{
Leszek~G\k asieniec \inst{1} \and Ralf~Klasing \inst{2} \and Christos~Levcopoulos \inst{3}\\ Andrzej~Lingas \inst{3} \and Jie~Min \inst{1} \and Tomasz~Radzik \inst{4}}
\institute{{Department of Computer Science}, {University of Liverpool}, {Liverpool, UK},
\email{\{l.a.gasieniec, J.Min2\}@liverpool.ac.uk}.

\and {CNRS}, {LaBRI}, {Universit\'e de Bordeaux}, {France},
\email{ralf.klasing@labri.fr}.
\and {Department of Computer Science}, {Lund University}, {Lund, Sweden},
\email{\{christos.levcopoulos, andrzej.lingas\}@cs.lth.se}.
\and {Department of Informatics}, {King's College London}, {London, UK}, 
\email{tomasz.radzik@kcl.ac.uk}.
}

\titlerunning{Bamboo Garden Trimming Problem}

\authorrunning{L. G\k asieniec, R. Klasing, C. Levcopoulos, A. Lingas, J. Min, T. Radzik}

\sloppy
\maketitle

\begin{abstract}

A garden $G$ is populated by $n\ge 1$ bamboos $b_1, b_2, ..., b_n$ with the respective daily growth
rates

$h_1 \ge  h_2 \ge \dots \ge h_n$. 
It is assumed that the initial heights of bamboos are zero.
The robotic gardener maintaining the garden regularly
attends bamboos and trims them to height zero
according to some schedule. The {\sl Bamboo Garden Trimming Problem} (BGT) is to
design a perpetual schedule of cuts to maintain the elevation of the bamboo garden as low as possible.
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.
The objective is to design a perpetual schedule of servicing which minimizes
the maximum (weighted) waiting time for servicing.

We consider two variants of BGT.
In {\sl discrete} BGT the robot trims only one bamboo at the end of each day.

In {\sl continuous} BGT
the bamboos can be cut at any time, however, the robot needs time to move from one bamboo to the next.

For discrete BGT, we show a simple $4$-approximation algorithm
and, by exploiting relationship between BGT and the classical Pinwheel scheduling problem, 
we derive a $2$-approximation algorithm for the general case and a
tighter approximation when the growth rates are balanced.
A by-product  of this last approximation algorithm is that it  
settles one of the conjectures about the Pinwheel problem.
For continuous BGT, we propose approximation algorithms
which achieve 
approximation ratios $O(\log (h_1/h_n))$ and $O(\log n)$.

\end{abstract}

\section{Introduction}\lambdabel{sec:Intro}

We consider a perpetual scheduling problem in which $n$ 
(possibly virtual)
machines need to be attended (serviced) with {\sl known} but possibly different frequencies, i.e.\
some machines need to be attended more often than others. 
The frequencies of attending individual machines 
are specified as positive weights $h_1, h_2, \dots, h_n$ 
and the objective is to design a perpetual schedule of attending the machines 
which minimizes the maximum
weighted time any individual machine waits for the next service.
The same optimization problem arises when a data stream keeps filling a collection of $n$ 
buffers according to a known distribution: buffer $i$ receives $h_i$ units of data 
in each unit of time. 
The objective is to design a perpetual schedule of emptying the buffers 
which minimizes the maximum
occupancy of any individual buffer.

We model such perpetual scheduling problems using the following metaphor of 
the {\sl Bamboo Garden Trimming (BGT) Problem}.
A collection (garden) of $n$ bamboos $b_1, b_2, \ldots, b_n$ 
with known respective daily growth rates $h_1, h_2, \dots, h_n$.
We assume that these growth rates are already arranged into a non-increasing sequence:
$h_1 \ge  h_2 \ge \dots \ge h_n > 0$.
Initially the height of each bamboo is set to zero. 
The robotic gardener maintaining
the garden trims bamboos to height zero according to some schedule.
The height of a bamboo $b_i$ at time 
$t \ge 0$ is equal to $(t - t') h_i$, where $t'$ is the last time when
this bamboo was trimmed, or $t' = 0$, if it has never been trimmed by time~$t$.

The main task of the BGT problem 
is to design a perpetual schedule of cuts to keep the highest bamboo in the garden as low as possible, while complying with some specified constraints on the timing of cutting. 
The basic constraints considered in this paper 
are that the gardener can cut only one (arbitrary) bamboo at the end of each day and
is not allowed to attend the garden at any other times.
Once the gardener has decided which bamboo to trim in the current round (at the end of the current day),  then 
the action of actual trimming is instantaneous. 

Referring back to the two scheduling problems mentioned earlier, 
the heights of the growing bamboos would represent the weighted times the machines 
wait for the next service, or the current occupancy of the data buffers.
The action of cutting a bamboo $b_i$ at the end of the current day represents 
attending machine $i$ or emptying buffer $i$ in the current time slot.

Other problems which can be modeled by BGT 
include the perpetual testing of virtual machines in cloud systems~\cite{AKG15}.
In such systems frequency in which virtual machines are tested for undesirable symptoms vary depending on the importance of dedicated cloud
operational mechanisms.

BGT is also a natural extension of several classical algorithmic problems with
the focus on {\em monitoring} and {\em mobility}, including the {\em Art Gallery Problem}~\cite{ntafos_gallery_1986} 
and its dynamic extension 

 called the {\em $k$-Watchmen Problem}~\cite{urrutia_art_2000}.
In a more recent work on {\em fence patrolling}~\cite{collins_optimal_2013,czyzowicz_boundary_2011} the studies
focus on monitoring vital (possibly disconnected) parts of a linear environment where each point is expected to 
be attended with the same frequency. 

The authors of~\cite{CGK+15} study monitoring linear environments by robots prone to faults.

Our paper focuses on the case where each vital part of the environment has its own, 
possibly unique urgency factor. 
This makes it related to {\em periodic scheduling}~\cite{serafini_mathematical_1989}, 
a series of papers 

on the {\em Pinwheel\/} problems~\cite{chan_general_1992,chan_schedulers_1993,holte_pinwheel:_1989}
including the {\em periodic Pinwheel\/} problem~\cite{holte_pinwheel_1992,lin_pinwheel_1997} and
the {\em Pinwheel scheduling\/} problem~\cite{romer_algorithm_1997},
as well as the concept of {\sl P-fairness} in sharing multiple copies of 
some resource among various tasks~\cite{baruah_proportionate_1996,baruah_pfair_1998}.

We consider two variants of the BGT problem. 
The constraint that only one bamboo is cut at the end of each day (round) defines
{\em discrete\/} BGT.
In the second variant, {\em continuous\/} BGT, 
we assume that for any two bamboos $b_i$ and $b_j$,
we know the time $t_{i,j} > 0$ (which may be fractional) 
that the robot needs to relocate from $b_i$ to $b_j$.

In this variant 
the time when the next bamboo is trimmed 
depends on how far that bamboo is from the bamboo which has just been trimmed.
As in discrete BGT, when the robot arrives at the bamboo to trim it, 
the actual action of trimming is instantaneous.

In this paper we consider symmetric travel times
(that is, $t_{i,j} = t_{j,i}$) and assume that 
the robot travels always along the fastest route, so the travel times 
satisfy the triangle inequality.
We also assume that the robot is initially at the location of $b_1$.
Discrete BGT is the special case of continuous BGT when all travel times $t_{i,j}$, for $i\neq j$, are the same,
while metric TSP is the special case of continuous BGT when all growth rates $h_i$ are the same.

Previous work on problems of similar nature as the continuous BGT includes recent work on 
patrolling~\cite{collins_optimal_2013,czyzowicz_boundary_2011,CGK+15,KaKo15}.

In both cases, discrete and continuous, we consider algorithms ${\cal{A}}$ 
which for an input instance $I$
(of the form $\lambdangle h_i:\: 1\le i \le n\rangle$ 
in the discrete case and $[\lambdangle h_i:\: 1\le i \le n\rangle$, $\lambdangle t_{i,j}:\: 1\le i,j\le n\rangle]$
in the continuous case) 
produce a perpetual (trimming) schedule ${\cal{A}}(I)$, that is, 
a sequence of indices of bamboos $(i_1, i_2, \ldots)$ which defines the order  
in which the bamboos are trimmed.
We are mainly interested in the {\em approximation ratios\/} of such algorithms, 
which are defined in the usual way.
For an input instance $I$ and a trimming schedule ${\cal{S}}$ for~$I$, 
let ${\mbox{\it MH}}({\cal{S}})$ denote the supremum of the heights of bamboos over all times $t \ge 0$ when the trimming 
proceeds according to schedule ${\cal{S}}$, and
let ${\mbox{\it OPT}}(I)$ denote 
the infimum of ${\mbox{\it MH}}({\cal{S}})$ over all schedules ${\cal{S}}$ for~$I$.

The approximation ratio of 
a schedule ${\cal{S}}$ is defined as ${\mbox{\it MH}}({\cal{S}}) / {\mbox{\it OPT}}(I)$ and
the approximation ratio of an algorithm 
${\cal{A}}$ is the supremum of ${\mbox{\it MH}}({\cal{A}}(I)) / {\mbox{\it OPT}}(I)$ over all input instances $I$.

Regarding the time complexity of BGT algorithms,
we aim at polynomial preprocessing time followed by computation of the consecutive indices of 
the schedule in poly-logarithmic time per one index. 
We will call algorithms with such performance simply polynomial-time (BGT) algorithms.
The computational complexity of continuous BGT is related to the complexity of TSP, as the latter is a special case of the
former. To discuss computational complexity of discrete BGT, we introduce first a lower bound on the height 
of schedules.

For each instance $I$ of discrete BGT with the sum of the growth rates $H=h_1+h_2+\dots+h_n$,
a simple and natural lower bound 
on the maximum height of a bamboo in any schedule 
is ${\mbox{\it OPT}}(I) \ge H$.
Indeed, while the heights of all bamboos are at most $H' < H$,
then during each day the {\sl total height} of all bamboos,
that is, the sum of the current heights of all bamboos,
increases at least by $H - H' > 0$ (the total growth over all bamboos is $H$ but only one
bamboo, of height at most $H'$, is cut).
Thus on some day within the first $\lfloor n H'/(H - H') \rfloor + 1$ days 
the total height of the bamboos must exceed $n H'$, so the height of one 
of the bamboos must exceed $H'$.
Observe also that it cannot happen that the maximum height of a bamboo approaches $H$
but never reaches $H$, because there are only finitely many possible heights of bamboos 
which are less than $H$.

There are instances with ${\mbox{\it OPT}}(I) = H$. For example, for the input 
instance $I = (1/2, 1/4, 1/4)$, all bamboos are kept within the $H= 1$ height 
by the schedule with period $(b_1, b_2, b_1, b_3)$.
An example of an input instance with ${\mbox{\it OPT}}(I) > H$ is 
$I = (7/15, 1/3, 1/5)$, for which $H = 1$ 
but ${\mbox{\it OPT}}(I) = 4/3$.
For this instance, 
the schedule with period $(b_1,b_2,b_1,b_2,b_1,b_3)$ does not let any bamboo grow 
above the height $4/3$.
On the other hand, a schedule which keeps the heights of $b_1$ and $b_2$ 
strictly lower than $4/3$ must cut $b_1$ every other day, implying that $b_2$ must also be cut every other day (after the initial couple of days).
Thus, after the initial couple of days, there are no further days available to cut $b_3$, so its height 
grows to infinity.

\setcounter{footnote}{0}
The computational complexity of discrete BGT is related to the computational complexity of the Pinwheel problem~\cite{holte_pinwheel:_1989}, which can be viewed as a special case of discrete BGT.
The Pinwheel complexity results presented in~\cite{holte_pinwheel:_1989} imply that 
for a given $K \ge H$, if there is a schedule with height at most $K$, then there is a cyclic schedule with height 
at most $K$, but the shortest such schedule can have exponential length.\footnote{
Exponential in the size of the input, assuming that the growth rates are rational numbers given as pairs of integers.
} 
This implies that the decision version of discrete BGT can be solved by considering all cyclic schedules 
of up to exponential length, and this can be implemented in PSPACE. 
Further from~\cite{holte_pinwheel:_1989}, 
while the cyclic schedules of height $H$ can also have exponential length, they have concise polynomial-size
representations, and there is a polynomial-time algorithm for checking if a given concise representation of 
a cyclic schedule of height $H$ is valid. This implies that the restricted decision version of discrete BGT 
which asks if there is a schedule of height $H$ is in NP. 
There have been some further complexity results for the Pinwheel problem, with direct implications for the complexity
of discrete BGT (see~\cite{DBLP:journals/networks/BallerEHS20}), but all in all, the complexity of 
the Pinwheel problem remains a long-standing open question.

In related research on minimizing the maximum occupancy of a buffer in a system of $n$ buffers,
the usual setting is a game between the player and the adversary
\cite{bender-etal-2015,cinderella,chrobak-etal-ICALP2001}.
The adversary decides how the fixed total increase of data in each round is distributed among the buffers and tries
to maximize the maximum occupancy of a buffer. 
The player decides which 
buffer (or buffers, depending on the variant of the problem)
should be emptied next and tries to minimize the maximum buffer size. 
The upper bounds developed in this more general context can be translated into upper bounds for our
BGT problems, but our aim is to derive tighter bounds for the case 
when the rates of growth of the occupancy of buffers, or the rates of growth of bamboos in our language, 
are fixed and known.

Probably the most natural strategy to keep the elevation of the bamboo garden low is the greedy approach
of always moving next to, and cutting, the currently highest bamboo. 
This approach, called {\sl \mbox{Reduce-Max}}, was considered recently in the context of 
periodic testing of virtual machines in cloud systems~\cite{AKG15}, and 
was also studied in the adversarial setting of the buffer minimization problems mentioned above.
The results presented in~\cite{cinderella} imply a tight upper bound of $H\cdot(H_{n-1} + 1) = \Theta(H \log n)$
on ${\mbox{\it MH}}({\cal{S}})$ for schedules ${\cal{S}}$ produced by 
$\mbox{Reduce-Max}$ for a variant of the discrete BGT with
the adversary which in each round arbitrarily 
distributes the total daily growth of $H$ among the bamboos.
Here 
$H_k = \sum_{i=1}^{k}\frac{1}{k} = \Theta(\log k)$ is the $k$-th harmonic number.
While this $O(H \log n)$ upper bound applies obviously 
also to 
our non-adversarial discrete BGT, 
when the growth rates are fixed,
it was a long standing open question 
whether there were instances for which $\mbox{Reduce-Max}$ 
lets some bamboos grow to heights $\Omega(H \log n)$, or
even to heights $\omega(H)$.
The experimental work presented in~\cite{AKG15} pointed towards a conjecture that $\mbox{Reduce-Max}$
keeps the maximum bamboo height within $O(H)$, and 
the question has been finally recently answered in~\cite{BGLPS21}, where 
a bound of $9H$ on the maximum bamboo height under the 
$\mbox{Reduce-Max}$ algorithm was proven. 

\paragraph{
Our contributions and related work.}

In the preliminary version~\cite{DBLP:conf/sofsem/GasieniecKLLMR17} of this 
paper, we introduced a modification of $\mbox{Reduce-Max}$, which we 
called $\mbox{Reduce-Fastest}$, to
show the first simple greedy algorithm
achieving constant approximation ratio.
$\mbox{Reduce-Fastest}$ works in the following way.
Keep track of the ``tall'' bamboos, defined as having the 
current height at least $x\cdot H$ (where $x$ is 
a parameter of the algorithm), and 
cut in each step the tall bamboo with the highest growth
rate (no cutting, if there is no tall bamboo).
In Section~\ref{sec:DiscreteBGT-online},
we present a detailed proof that the approximation ratio
of $\mbox{Reduce-Fastest}$ for $x = 2$ is at most $4$.
Subsequently to our work, 
it has been proven in~\cite{BGLPS21} that 
using the $\mbox{Reduce-Fastest}$ strategy
an approximation ratio of $2.62$ 
can be achieved,
and that, as mentioned above, the $\mbox{Reduce-Max}$
strategy also achieves constant approximation
ratio.
\cite{BGLPS21} also presents efficient 
implementations of these two heuristics.

We refer informally 
to BGT algorithms like $\mbox{Reduce-Max}$ and $\mbox{Reduce-Fastest}$ as 
{\em online scheduling}. These algorithms are based on 
simple greedy strategies, the trimming schedule is 
revealed while the cutting progresses, and 
the whole cutting process would naturally
adapt to changing growth rates.
An alternative {\em offline 
scheduling} pre-computes the whole (cyclic) schedule. 
This approach would sacrifice 
the flexibility offered by simple greedy 
strategies but hopefully would give better 
approximation ratios.
Indeed, using the Pinwheel results given in~\cite{holte_pinwheel:_1989}, one can
easily obtain a $2$-approximation (offline) scheduling algorithm
for discrete BGT. 
An efficient implementation 
of this algorithm was developed
in~\cite{BGLPS21}.
Recently, \cite{Ee21} has shown
an offline scheduling algorithm, 
also based on Pinwheel results, which
guarantees $12/7$-approximation.

In Section~\ref{sec:DiscreteBGT-offline} we present our main approximation algorithm 
for discrete BGT, 
which is an offline algorithm derived by 
further exploration of 
the relation between discrete BGT and
the Pinwheel problem and has approximation ratio
$(1+O(\sqrt{h_1/H}))$. 
The benefits of the relation between the discrete BGT and Pinwheel problems extend both ways. 
On the one hand, our approximation algorithm uses 
properties of the Pinwheel problem. On the other hand, 
the approximation ratio which we achieve settles one of
the conjectures about the Pinwheel problem as explained in Section~\ref{sec:BGT-Pinwheel}.

In Section~\ref{sec:ContinuousBGT}, we show algorithms for continuous BGT
with approximation ratios $O(\log({h_1}/{h_n}))$ and $O(\log n)$.\footnote{
As Metric TSP is a subproblem of continuous BGT, it is NP-hard to approximate
continuous BGT with a factor better than 123/122 \cite{KLS15}.
}

We also discuss how tight these approximation ratios are. 
We show instances of
continuous BGT such that for any schedule the maximum
bamboo height is greater by a $\Theta(\log n)$
factor than the lower bounds which we use in the analysis of approximation ratios. 
Thus for these input instances our $O(\log n)$-approximation
algorithm computes in fact schedules with constant approximation ratios.
We also show instances for which this algorithm computes $\Theta(\log n)$-approximate
schedules.

\section{Discrete BGT problem and Pinwheel}
\lambdabel{sec:BGT-Pinwheel}

The input of the Pinwheel problem is a sequence 
$V= (f_{1},f_{2},\ldots,f_{n})$ of integers $2 \le f_{1} \le f_{2}\le \ldots \le f_{n}$
called ({\em pinwheel\/}) {\em frequencies}.
The objective is to specify an infinite sequence $S$ of indices 
drawn from the set ${1,2,\ldots,n}$ such that
for each index $i$, any sub-sequence of $f_{i}$ 
consecutive elements in $S$
includes at least one index $i$, 
or to establish that such a sequence does not exists. 
A sequence $S$ with this property is called a schedule of $V$, and if such a sequence does not exist, then
we say that the sequence of frequencies $V$
is not feasible or that it cannot be scheduled.
The Pinwheel problem is a special case of  discrete BGT: 
an input instance $(f_{1},f_{2},\ldots,f_{n})$ of Pinwheel is feasible if, and only if,
the optimal (minimum) height for the input instance 
$(1/f_{1}, 1/f_{2},\ldots, 1/f_{n})$ of discrete BGT is at most $1$.

The Pinwheel problem was introduced in~\cite{holte_pinwheel:_1989}, 
where some complexity 
results were presented and some classes of feasible sequences of frequencies were established.
It is easy to see
that it is not possible to schedule any instance $V$ whose {\em density} 
$D(V)\equiv \sum_{i=1}^{n}{1}/{f_{i}}$ is greater than $1$,
since in any feasible schedule each frequency $f_i$ takes 
at least ${1}/{f_{i}}$ fraction of the slots.\footnote{
More precisely, in each prefix of length $T-f_n$ of a feasible schedule, where $T$ is
arbitrarily large,
each frequency $f_i$ must take at least $(1/f_i)(T-f_i)$ slots, implying 
$\sum_{i=1}^{n}{1}/{f_{i}} \le 1$.
}
(This upper bound of~$1$ on the density of a feasible instance of the Pinwheel problem 
is a special case of the lower bound of $H$ on the maximum height for
an instance of discrete BGT.) 
The sequence of frequencies $(2,4,4)$ is an example of a feasible 
instance of the Pinwheel problem with density~$1$.
On the other hand,
the input instances $(2,3,M)$, where $M$ is an arbitrarily large integer,
show that there are instances with densities arbitrarily close to $5/6$ which are not feasible.
One of the conjectures for the Pinwheel problem, which remains open, 
is that $5/6$ is the universal threshold guaranteeing feasibility of input instances.
That is, it has been conjectured (ever since the pinwheel problem was introduced) that
any instance with density at most $5/6$
can be scheduled.
The current best proven bound is $3/4$~\cite{fishburn_pinwheel}.

Our work is related to another conjecture for the Pinwheel problem, made by 
Chan and Chin~\cite{chan_general_1992},
that when the first frequency $f_1$ keeps increasing, then the density threshold guaranteeing 
feasibility keeps increasing to $1$.
To be more precise, 
let ${\cal{V}}$, ${\cal{V}}_{yes}\subseteq {\cal{V}}$ and ${\cal{V}}(f,\Delta)\subseteq {\cal{V}}$
denote the set of all instances $V$
of the Pinwheel problem with density $D(V) \le 1$, the set of all feasible instances and 
the set of instances with $f_1 = f$ and density $D(V) \le \Delta$, respectively. 
Define
$d(f) \equiv \sup\{ \Delta:\; {\cal{V}}(f,\Delta) \subseteq {\cal{V}}_{yes}\}$ as
the density threshold guaranteeing feasibility of instances with the 
first frequency equal to $f$. 
That is, each input instance $(f_1=f, f_2, f_3, \ldots)$ with density 
less than $d(f)$ is feasible, while for each $
$\Box$silon >0$, there 
is an infeasible instance with density less than $d(f)+
$\Box$silon$.

Chan and Chin~\cite{chan_general_1992,chan_schedulers_1993} conjecture 
that $\lim_{f\rightarrow\infty} d(f) = 1$, consider a number 
of heuristics for the Pinwheel problem (referred to as  {\em schedulers})
and analyze  the guarantee density threshold
$$d_{\cal{A}}(f) \equiv \sup\{ D:\; 
\mbox{heuristic ${\cal{A}}$ schedules each instance in  ${\cal{V}}(f,D)$}\}$$
for each considered heuristic~${\cal{A}}$.

They derive lower bounds $\ell_{\cal{A}}(f)$ on the values $d_{\cal{A}}(f)$, but 
for each of their lower bounds, $\lim_{f\rightarrow\infty} \ell_{\cal{A}}(f)$ is strictly less than $1$,
which leaves possibility that $\lim_{f\rightarrow\infty} d_{\cal{A}}(f)$ 
is also strictly less than~$1$.\footnote{
Chan and Chin~\cite{chan_general_1992,chan_schedulers_1993} 
showed that for some algorithms which they considered $\lim_{f\rightarrow\infty} d_{\cal{A}}(f)$
is actually strictly less than $1$. For the other algorithms, they left unanswered the question whether $\lim_{f\rightarrow\infty} d_{\cal{A}}(f) = 1$.}
Thus~\cite{chan_general_1992,chan_schedulers_1993} left open the question of designing an algorithm ${\cal{A}}$ for which 
$\lim_{f\rightarrow\infty} d_{\cal{A}}(f) = 1$, and there have not been other results in this direction prior to our work.
Such an algorithm 
would immediately imply 
that $\lim_{f\rightarrow\infty} d(f) = 1$.

Our $(1+O(\sqrt{h_1/H}))$-approximate polynomial-time algorithm for discrete BGT
applied to input instances $(1/f_{1}, 1/f_{2},\ldots, 1/f_{n})$
is a polynomial-time scheduler for Pinwheel input instances $(f_{1},f_{2},\ldots,f_{n})$
with the guarantee density threshold $1-O(\sqrt{1/f_1})$.
This threshold tends to $1$ with increasing $f_1$, proving the conjecture that 
$\lim_{f\rightarrow\infty} d(f) = 1$.

To see that this Pinwheel scheduler has indeed 
the guarantee density threshold $1-O(\sqrt{1/f_1})$,
let $C$ be a constant such that the approximation ratio of our algorithm
for discrete BGT is at most $1+ C\sqrt{h_1/H}$.
If the density $D(V)$ of a Pinwheel instance $V = (f_{1},f_{2},\ldots,f_{n})$ is at most $1 - C/\sqrt{f_1}$, 
then the BGT schedule computed for the input $(1/f_{1}, 1/f_{2},\ldots, 1/f_{n})$
does not let the height of any bamboo
go above  (note that $H= D(V)$):
\begin{eqnarray*}
D(V)\left((1+ C\sqrt{(1/f_1)/D(V)}\right) & = & D(V) + C\sqrt{D(V)/f_1} \\
& \le & 1 - C/\sqrt{f_1} + C\sqrt{D(V)/f_1} \; \le  \: 1.
\end{eqnarray*}
Thus the computed schedule is a feasible schedule for the Pinwheel instance.

\section{Discrete BGT by online scheduling}\lambdabel{sec:DiscreteBGT-online}

We consider two types of algorithms for the discrete variant of BGT.
An {\em online\/} algorithm keeps track of the current heights of the bamboos
and decides which bamboo should be cut next on the basis of simple queries 
like ``what is the tallest
bamboo?'' (as in $\mbox{Reduce-Max}$ algorithm), 
or ``what is the fastest growing bamboo with the height above some
threshold?''  (as below in $\mbox{Reduce-Fastest}$ algorithm).
Such queries can be answered without knowing the whole distribution of growth rates.
An {\sl offline} algorithm determines which bamboo is to be trimmed during a particular round 
by first preprocessing the input (the sequence of the daily growth rates) into  
a representation of the full perpetual schedule. After the preprocessing,
the schedule is produces with some small computational effort per each step (that is, per each 
cutting decision).

Online scheduling is more flexible since it 
can adapt, if the growth rates change. On the downside, the performance analysis of
online scheduling is more complex and the approximation bounds tend to be weaker.
Offline scheduling is less flexible since changes of the growth rates require re-doing the preprocessing, 
but leads to stronger approximation bounds.

We note that our
online versus offline characterization of BGT algorithms does not 
refer to the availability of input (in both cases the whole input is known in advance) but only
indicates the general nature of algorithms.

We present in this section a simple constant-ratio online scheduling algorithm, 
which is obtained by the following modification of $\mbox{Reduce-Max}$.
We cut next the fastest growing `tall' 
bamboo, where tall bamboos are the bamboos
with the current heights at least 
$x\cdot H$, for a given parameter $x>1$.
We call this algorithm \mbox{Reduce-Fastest}($x$) and show the following approximation bound.

\begin{theorem}\lambdabel{th:4appr}
{\rm \mbox{Reduce-Fastest}(2)} is a 4-approximation algorithm for discrete BGT.
\end{theorem}

\begin{proof}

We consider the execution of $\mbox{Reduce-Fastest}(x)$ for a fixed value $x > 1$.
Without loss of generality, we assume that if there are two or more bamboos with the 
same fastest growth rate among the bamboos with the current height at least $x\cdot H$, then 
\mbox{Reduce-Fastest}\/ chooses for trimming the bamboo with the smallest index.
Thus the height of bamboo $b_1$ is always less than $x H + h_1 \le (x+1)H$.

We consider now a bamboo $b_i$, for an arbitrary $2 \le i \le n$,
and assume that it reaches the height at least
$C\cdot H$ for some constant $C\ge x+1$.

At any time the heights of bamboos belong to two disjoint regions: 
the lower region $[0,x H)$ and the upper region $[x H, \infty)$.
At some point bamboo $b_i$ must stay in the upper region for at least

$t  = \left\lfloor{(C-x)H}/{h_i}\right\rfloor$ consecutive rounds to
reach the height $C\cdot H$.
That is, during each of these $t$ rounds, $b_i$ has height at least $xH$  
but is not cut.

We consider a period of $t$ consecutive rounds 
when bamboo $b_i$ remains in the upper region. 
At each of these rounds,
trimming of bamboo $b_i$ is blocked by trimming of another bamboo $b_j$ for some $j < i$,
by the definition of {\rm \mbox{Reduce-Fastest}(2)}.
The number of times when the same bamboo $b_j$ can block bamboo $b_i$ during this period is at most 
$t_j=1+\lfloor{t}/{f_j}\rfloor$, where 
$f_j=\lceil{x H}/{h_j}\rceil$ is the number of rounds 
bamboo $b_j$ needs to climb back to the upper region after trimming.
Thus

\[
t \le \sum_{j=1}^{i-1}t_{j} = \sum_{j=1}^{i-1} 
   \left(1+ \left\lfloor\frac{t}{f_j}\right\rfloor\right)
   \le t \left(\frac{i-1}{t} + \sum_{j=1}^{i-1} \frac{1}{f_j}\right),
\]
hence
\begin{equation}\lambdabel{kjl32a}
\frac{i-1}{t} + \sum_{j=1}^{i-1} \frac{1}{f_j} \ge 1.
\end{equation}
Since $h_i\le{H}/{i}$ and $C - x \ge 1$, we have
\begin{equation}\lambdabel{hj2es}
t  = \left\lfloor\frac{(C-x)H}{h_i}\right\rfloor
   > (C-x)i - 1 
   \ge (C-x)(i-1).
\end{equation}
Inequalities~\eqref{kjl32a} and~\eqref{hj2es} imply
\[
1 \le \frac{i-1}{t} + \sum_{j=1}^{i-1} \frac{1}{f_j}
   <  \frac{1}{C-x} + \sum_{j=1}^{i-1} \frac{h_{j}}{xH}
   < \frac{1}{C-x}+\frac{1}{x}.
\]
We rewrite $1 < 1/(C-x)  + 1/x$ to
\[
C < 2 + \left((x-1) + \frac{1}{x-1}\right),
\]

and observe that 
the right-hand side above is minimized for $x= 2$ and for this value gives $C < 4$.
Thus during the execution of \mbox{\mbox{Reduce-Fastest}(2)}, no bamboo can reach the height $4H$,
so the approximation ratio of this algorithm is at most~$4$.

$\Box$\end{proof}

In addition to approximation guarantees,
the time complexity of BGT heuristics is 
also important.
Efficient implementations of \mbox{\mbox{Reduce-Max}} and \mbox{\mbox{Reduce-Fastest}}
were presented in~\cite{BGLPS21}. 
Below we briefly indicate the main ideas.

For \mbox{\mbox{Reduce-Max}},
use a parametric priority queue, where keys 
are linear functions $at+b$ of
a single parameter $t$. 
Maintain such a queue 
containing the value-key entries 
$(i, h_it - h_it_i)$, where $t_i$ is the last 
step when bamboo $b_i$ was cut. 
Thus $h_i(t - t_i)$ is the height of $b_i$ at step $t \ge t_i$.

In the current step $T$, 
delete from the queue the entry with 
the maximum key for $t = T$
(using the delete-max operation of the 
parametric priority queue)
obtaining the current tallest bamboo $b_i$.
Cut this bamboo and insert to the queue
the entry $(i,h_it - h_iT)$.
The running time of one step is 
$O(\log^2 n)$, using, for example,
the implementations of 
parametric priority queues proposed 
in~\cite{10.5555/365411.365793,OVERMARS1981166}.

For \mbox{\mbox{Reduce-Fastest}$(x)$}, let
$Z$ be the set of the current tall 
bamboos, that is, 
the bamboos which have reached height
$x$ by the current step~$T$, and let $Y_t$,
for $t\ge T$, be the set of the bamboos
which will reach height $x$ at step 
$t$.
Maintain set $Z$ and all non-empty 
sets $Y_t$
as priority queues
with value-key entries $(i, h_i)$
of bamboo indices and heights.
In addition, keep
the pairs $(t,Y_t)$, for non-empty sets
$Y_t$, in a dictionary ($t$ is the key).

During the current step $T$:
remove $Y_T$ from the dictionary 
and merge it into $Z$ (if $Y_T$ exists),
remove from $Z$ the pair $(i,h_i)$ with the 
greatest $h_i$ (the fastest growing tall bamboo),
cut bamboo $b_i$ and insert $(i,h_i)$ 
to the set $Y_t$ for
$t = T + \lceil x/h_i \rceil$
(this $t$ is the next step when $b_i$ reaches height $x$).
The running time of one step 
is $O(\log n)$, using 
a mergeable priority queue with $O(\log n)$ 
worst-case running time per each operation
(e.g.~\cite{DBLP:conf/stoc/BrodalLT12}).

\section{Discrete BGT by offline scheduling}\lambdabel{sec:DiscreteBGT-offline}

In this section we focus on offline scheduling which permits tighter approximation results.
These results are achieved by exploring 
the relationship between BGT and the Pinwheel scheduling problem.
Some known facts about Pinwheel scheduling 
give immediately a 2-approximation BGT algorithm. Our main result in this section is 
a $(1+O(\sqrt{h_1/H}))$-approximation algorithm. 
One of the consequences of this approximation algorithm is that it settles the conjecture made for the Pinwheel problem
that if the first (smallest) frequency keeps increasing, the 
density threshold which guarantees feasibility increases to $1$ (cf.~Section~\ref{sec:BGT-Pinwheel}).  

\subsection{Reducing discrete BGT to Pinwheel scheduling}\lambdabel{s:pinwheel}

We use the notation for the Pinwheel problem introduced in Section~\ref{sec:BGT-Pinwheel}.
Each feasible input sequence of frequencies $f_1 \le f_2 \le \cdots \le f_n$ has

the density $D = \sum_{i=1}^{n} 1/f_i$ at most one.

We also know that any instance with density at most $3/4$ is feasible~\cite{fishburn_pinwheel}, 
and it is conjectured that in fact any instance with density at most $5/6$ is feasible.

To see the relationship between the BGT and the Pinwheel
problem, define for a BGT input instance $I = (h_1 \ge  h_2 \ge \dots \ge h_n > 0)$
the sequence of frequencies
$f'_{i}=H/h_{i}$, $i = 1,2, \ldots, n$.
This sequence $(f'_1, f'_2, \ldots, f'_n)$
is a \emph{pseudo-instance} of Pinwheel (pseudo, since these frequencies
are rational numbers rather than integers) with  density:
\[
D'={\displaystyle \sum_{i=1}^{n}}\frac{1}{f'_{i}}
={\displaystyle \sum_{i=1}^{n}}\frac{h_{i}}{H}=1.
\]
We multiply the frequencies $f'_i$ by $1+\delta$ to obtain another 
pseudo-instance $f''_{i}= f'_{i}(1+\delta)$, $i = 1,2, \ldots, n$, 
with the density reduced to $1/(1+\delta) <1$,
where $\delta>0$ is a suitable parameter.

Finally, we obtain a (proper) instance $V(I,\delta) = (f_1, f_2, \ldots, f_n)$ of the Pinwheel problem
by reducing each frequency $f''_i$ to an integer $f_i \le f''_i$.
Thus we require that the integer frequencies~$(f_i)$ are not greater than the rational frequencies $(f''_i)$, but
we do not specify at this point their exact values, 
leaving this to concrete algorithms.
Reducing frequencies $(f''_i)$ to $(f_i)$ increases the density of the sequence.
The room for this increase of the density was made by 
the initial decrease of the density to $1/(1+\delta)$.

 

\begin{lemma}\lambdabel{l:delta}
If $I$ is an instance of BGT, $\delta > 0$ and an instance
$V(I,\delta)$ of the Pinwheel problem is feasible, then a feasible schedule for
this Pinwheel instance $V(I,\delta)$ is
a $(1+\delta)$-approximation schedule for the BGT instance $I$.
\end{lemma}

\begin{proof}
In a feasible schedule for $V(I,\delta)$, two consecutive occurrences of an index $i$
are at most $f_i \le {H(1+\delta)}/{h_i}$ slots apart.
This means that if this schedule is used for the BGT instance $I$, then the height of $b_i$ 
is never greater than 
$h_i\cdot f_i \le H(1+\delta)$.

$\Box$\end{proof}

In view of Lemma~\ref{l:delta}, 
the goal is to get a {\em feasible\/} instance $V(I,\delta)$ of Pinwheel for as small value of $\delta$ as possible.
We also want to be able to compute efficiently a feasible schedule for $V(I,\delta)$, if one exists.
By decreasing the rational frequencies $f''_i$ to integer frequencies $f_i$, we increase the density of the Pinwheel instance,
making it possibly harder to schedule. Thus we should aim at decreasing the frequencies $f''_i$ only as much as necessary.
However, simply rounding down the frequencies $f''_i$ to the nearest integers might not be the best way since the 
integer frequencies obtained that way might not be sufficiently ``regular'' to imply a feasible schedule.

\subsubsection*{\bf A 2-approximation algorithm.}

To give a simple illustration how Lemma~\ref{l:delta} can be used, we refer
to the result from~\cite{holte_pinwheel:_1989} which says that any instance
of Pinwheel with frequencies being powers of 2 and the density at most 1 can be scheduled and 
a feasible schedule can be easily computed.

For an instance $I$ of BGT, we take the instance $V(I,1)$ where the frequencies $f''_i$ are rounded 
down to the powers of $2$. Multiplying first the frequencies by $2$ decreases the density to $1/2$.
The subsequent rounding down to the powers of $2$ decreases each frequency less than by half, so the density of the instance
increases less than twice. Thus the final instance $V(I,1)$ of Pinwheel has the density less than $1$ and all frequencies are
powers of $2$, so it can be scheduled 
and, by Lemma~\ref{l:delta}, its feasible schedule is a $2$-approximate schedule for the original BGT instance $I$.   

It was shown in~\cite{fishburn_pinwheel} that every instance of Pinwheel with density
not greater than $3/4$ is feasible and, tracing the proof given in~\cite{fishburn_pinwheel},
one can obtain an efficient scheduling algorithm for such instances.
For a BTG instance $I$, 
the Pinwheel instance $V(I,\delta) = (f_1, f_2, \ldots, f_n)$, where 
$\delta = 1/3 + h_1/H$ and 
$f_i = \lfloor (1+\delta)H/h_i \rfloor$ has density less than $3/4$ since
\[ \frac{1}{f_i} < \frac{1}{(1+\delta)H/h_i - 1} 
= \frac{h_i}{H} \cdot \frac{1}{1+\delta - h_i/H} 
\le \frac{h_i}{H} \cdot \frac{1}{1+\delta - h_1/H} 
= \frac{3}{4}\cdot \frac{h_i}{H}.
\]
Thus Lemma~\ref{l:delta} and Pinwheel schedules for instances with density 
at most $3/4$ give $(4/3 +h_1/H)$-approximate schedules for the BGT problem.
When $h_1/H$ decreases to $0$, then this approach gives 
approximation ratios decreasing to $4/3$,
improving on the $2$-approximation. 
We are, however, looking for an algorithm which would compute BGT schedules with 
approximation ratio decreasing to $1$ when $h_1/H$ decreases to $0$.

\omitthis{
\begin{proof}
Follows directly from Lemma~\ref{l:delta}.

$\Box$\end{proof}
}

\subsection{\bf A $(1+O(\sqrt{h_1/H}))$-approximation algorithm} 

\noindent
Our approach to a better BGT approximation is again through powers-of-two Pinwheel instances, 
as in the 2-approximation algorithm, but now we 
derive an appropriate powers-of-two instance through a process of gradual transformations.
We start with greater granularity of frequencies than powers of two by reducing 
the rational frequencies $f''_i = H(1+\delta)/h_i$  
to the closest values of the form $2^{k}(1+{j}/{C})$, where $k$ is an integer, $C=2^{q}$ for some
integer $q \ge 0$, and 
$j$ is an integer in $[0,C)$. 
We set the parameter $q$ in such a way that we always have $q \le k$, so the 
frequencies $2^{k}(1+{j}/{C})$ are integral, forming a proper instance of Pinwheel.
To show that the obtained instance $V(I,\delta)$ of Pinwheel is feasible, for a suitable choice of $\delta$,
and to construct a schedule for this instance,
we use the following two observations.

\vspace*{1ex}

\noindent
{\em Observation 1.} 
Let $V$ be an instance of Pinwheel which has two equal even frequencies $f_i = f_j = 2f$.
If the instance $V'$ obtained from $V$ by replacing these two frequencies with one frequency $f$ is feasible,
then so is instance $V$. 
Note that such updates of a sequence of frequencies do not change its density.
We obtain a schedule for $V$ from a schedule for $V'$ by replacing the occurrences of the frequency $f$
alternatingly with the frequencies $f_i$ and $f_j$.
In our algorithm we will be replacing pairs 
of equal frequencies $2^{k}(1+{j}/{C})$ with one frequency $2^{k-1}(1+{j}/{C})$.

\vspace*{1ex}

\noindent
{\em Observation 2.} 
Generalizing the previous observation,
let $V$ be an instance of Pinwheel which has $m$ equal frequencies $f_{i_1} = f_{i_2} =  \cdots  = f_{i_m} =  m f$, where 
$f$ is an integer.
If the instance $V'$ obtained from $V$ by replacing these $m$ frequencies with one frequency $f$ is feasible,
then so is instance $V$ and a schedule for $V$ can be easily obtained from a schedule for $V'$
(in the schedule for $V'$, for each $i \ge 0$ and $1 \le q \le m$, 
replace the $(im + q)$-th occurrence of $f$  with $f_{i_q}$). 
As before, such updates of a sequence of frequencies do not change its density. 

In our algorithm 
we will be combining $m_{j}=C+j$ frequencies $2^{k}(1+\frac{j}{C})$ into one frequency 
${2^{k}(1+{j}/{C})}/{m_{j}} = {2^{k}}/{C}$, which will 
be a power of 2. 

\vspace*{1ex}

We are now ready to describe our algorithm.

\vspace*{2.3ex}

\noindent
{\bf The Main Algorithm} \\[6pt]
{\bf Input}:
BGT instance $I = (h_1 \ge  h_2 \ge \dots \ge h_n)$. \\[3pt]
{\bf Output}: A (cyclic) perpetual schedule of $I$ specified by pairs $(p_i , q_i)$, for $1 \le i \le n$.
Item $b_i$ occurs in the schedule at positions $p_i + kq_i$, for $k \ge 0$.

\begin{enumerate}
\item 
Set the parameter $\delta = 3\sqrt{h_1/H}$.

 

 
Form a pseudo-instance $(f''_1 \le f''_2 \le \ldots \le f''_n)$ of Pinwheel, by setting
$f''_i = (1+\delta)H/h_i$.
The density of this pseudo-instance is ${1}/(1+\delta)$.

Let $min\ge 1$ be the largest integer such that $2^{min} \le f''_1$
(the setting of the parameter $\delta$ implies that $f''_1 \ge 2$ regardless of the value of $H/h_1$)
and let $max\ge min $ be the smallest integer
such that $2^{max+1} > f''_n$.

\item Reduce each frequency $f''_i$ to the closest value $f_i$ of the form 
$2^{k}(1+{j}/{C})$, where $k$, $C$ and $j$ are integers
such that $k\geq min$, $C = 2^q$ for $q =\lfloor min/2\rfloor$, and $0\le j \le C-1$.
These conditions imply that the new frequencies $f_i$ are integral.
Since this update of frequencies has reduced them at most by a factor of $1+{1}/{C}$, the density of the
whole sequence of frequencies  
increases at most by at a factor of $1+{1}/{C}$
to at most ${(1+{1}/{C})}/{(1+\delta)}$.

The sequence $(f_1, f_2, \ldots, f_n)$ is our (proper) instance $V(I,\delta)$ of the Pinwheel problem. 
The remaining steps compute a schedule of this sequence.
Steps 3-5 
use Observations~1 and~2, and further reductions of the frequencies if needed, to 
transform the sequence $(f_1, f_2, \ldots, f_n)$ 
to a sequence $(g_1, g_2, \ldots, g_r)$, $r \le n$ where all frequencies are  powers of $2$.

We refer to the range $[2^k, 2^{k+1})$ of frequencies as {\em layer\/} $k$, and to the 
set of frequencies of the same value $2^{k}(1+\frac{j}{C})$ as the {\em group} $j$ in layer $k$.

\item For $k = max, max-1, \ldots, min+1$,
apply Observation~1 in layer $[2^{k},2^{k+1})$ 
as many times as possible to combine pairs of the same frequencies 
different to powers of $2$,
pushing them down to the lower layer.

On the conclusion of this step, there is at most one frequency $2^{k}(1+\frac{j}{C})$, for each $k>min$ 
and $j\in(0,C).$

\item Apply Observation~2 in the layer $[2^{min},2^{min+1})$
until there are at most $C+j-1$ frequencies $2^{min}(1+\frac{j}{C})$ left, for any $j\in(0,C)$.

\item For $k = max, max-1, \ldots, min$, reduce all remaining frequencies in range $[2^{k},2^{k+1})$ which
are different to powers of $2$, group by group starting from the top group defined by $j=C-1$, 
and pushing each frequency down to the next lower group.
While progressing down through the groups,
keep applying Observation~1 whenever possible, if in a layer $k \ge min+1$, and Observation~2 
in the lowest layer for $k = min$. 

On the conclusion of this step, we have a sequence of frequencies 
$(g_1, g_2, \ldots, g_r)$, $r \le n$,
which are powers of $2$, 
but the density further increases by some value $\Delta D\ge 0$.
Thus the density of this final powers-of-$2$ instance $(g_i)$ of the Pinwheel problem 
is at most  ${(1+\frac{1}{C})}/{(1+\delta)}+\Delta D$.
We will show that the setting of the parameters $\delta$ and $C$ imply that this bound is at most $1$,
so sequence $(g_i)$ is feasible.

\item
Compute a cyclic schedule for the sequence of frequencies $(g_1, g_2, \ldots, g_r)$ 
using the algorithm for powers-of-2 Pinwheel instances 
from~\cite{holte_pinwheel:_1989}.
Such a schedule is specified by pairs $(p_i , q_i)$, for $1 \le i \le r$, which mean that 
the frequency $g_i$ is placed in the perpetual schedule of $(g_1, g_2, \ldots, g_r)$ 
at positions $p_i + kq_i$, for $k \ge 0$.

Expand the schedule of $(g_1, g_2, \ldots, g_r)$ to the schedule  of
$(f_1, f_2, \ldots, f_n)$ (and consequently the schedule of $(h_1, h_2, \ldots, h_n)$)
by tracing back the applications of Observations~1 and~2. 

\end{enumerate}

\noindent
The execution of steps 1-5 of the algorithm (the computation of the powers-of-2 
Pinwheel instance $(g_i)$) is illustrated in Figure~\ref{f:MainAlgo}.

The final step 6 of the algorithm is illustrated in Figure~\ref{f:CombineFreq}.
A frequency $f_j$ (computed in step 2) was subsequently (in steps 3--5) paired twice with other frequencies 
by applications of Observation~1 (contributing first to a new frequency $f_j/2$ and then to a new frequency $f_j/4$)
and ended up in a group of $10$ equal frequencies $f_j/4$,
which were replaced with one new frequency $g_i = f_j/40$ by an application of Observation~2.
Let the pair $(p_i, q_i)$ represent the positions of $g_i$ in the computed cyclic schedule of  $(g_1, g_2, \ldots, g_r)$:
frequency $g_i$ is placed at positions $p_i + kq_i$, for $k \ge 0$.

Expanding the schedule of $(g_1, g_2, \ldots, g_r)$ to the schedule  of
$(f_1, f_2, \ldots, f_n)$, 
every $40$-th occurrence of frequency $g_i$ 
is replaced by frequency $f_j$.
More precisely, we first replace every $10$-th occurrence of $g_i$ with the frequency $a$, starting 
from the $4$-th occurrence of $g_i$.
Then every second occurrence of $a$ is replaced with $y$, starting from the $2$-nd occurrence of $a$,
and finally every other occurrence of $y$ is replaced with $v$, that is, with the frequency $f_j$.
Thus frequency $f_j$ is placed in the schedule at positions $(p_i + 13 q_i) + k(40q_i)$.

\begin{figure}
\caption{Illustration of combining frequencies in the Main Algorithm.  In steps 3--5 of the algorithm,
frequency $f_j$ is paired twice with other frequencies by applications of Observation~1, creating a frequency $f_j/4$
(node $a$).
The resulting frequency is then put into a group of $10$ frequencies $f_j/4$ and this group 
is replaced with one new frequency $g_i = f_j/40$ by an application of Observation 2.
}
\end{figure}

\begin{figure}
\caption{Illustration of the execution of the Main Algorithm.
The top half shows the transformation of the frequencies for the layers other 
than the $min$ layer. The bottom half shows the transformations in the $min$ layer.}
\end{figure}

\begin{theorem}\lambdabel{th:main}

For each BGT input instance, the Main Algorithm 

computes a $(1+3\sqrt{h_1/H})$-approximation schedule.

\end{theorem}

\begin{proof}

We show that 
the density of the sequence of frequencies $(g_1, g_2, \ldots, g_r)$ computed 
in  step 5 of the algorithm is at most~$1$. Since these frequencies are powers of $2$, 
the sequence  $(g_1, g_2, \ldots, g_r)$ is feasible
and gives a $(1+\delta)$-approximation schedule for the initial BGT input instance 
(Lemma~\ref{l:delta}).

The density of the Pinwheel pseudo-instance $(f''_1, f''_2, \ldots, f''_n)$ is $D'' = 1/(1+\delta)$.
To bound the density $D$ of the Pinwheel instance $(f_1, f_2, \ldots, f_n)$, observe that 
if $f_i = 2^{k}(1+{j}/{C})$, then $f_i$ has been obtained from the rational frequency $f_i''$
such that 
\[ 2^{k}\left(1+\frac{j}{C}\right) \le f''_i < 2^{k}\left(1+\frac{j+1}{C}\right).
\]
This means that 
\[ f_i = 2^{k}\left(1+\frac{j}{C}\right) 
  > f''_i \left(1+\frac{j}{C}\right)/\left(1+\frac{j+1}{C}\right) = f''_i \frac{C+j}{C+j+1} \ge f''_i \frac{C}{C+1},
\]
so 
\[D \le (1+1/C) D'' = (1+1/C)/(1+\delta).
\]

Steps 3 and 4 of the algorithm transform the Pinwheel instance $(f_1, f_2, \ldots, f_n)$
using Observations 1 and 2, but without changing its density.

Step 5 further transforms the sequence of frequencies, increasing the density 
of the sequence whenever individual frequencies are reduced.
We bound separately the increase $\Delta D_{above}$
of the density when we modify the frequencies in layers 
$max, max -1, \ldots , min +1$,
and the increase $\Delta D_{min}$ of the density when we modify the frequencies in layer $min$.

\begin{eqnarray*}
\Delta D_{above} 
 & \le & \sum_{k=min+1}^{max} 
     \sum_{j=1}^{C-1} \frac{1}{2^k}\left( \frac{1}{1+(j-1)/C} - \frac{1}{1+j/C} \right) \\
& = & \sum_{k=min+1}^{max} 
     \frac{1}{2^k}\left( 1 - \frac{1}{1+(C-1)/C} \right)
     \le \frac{1}{2^{min}} \cdot \frac{C-1}{2C-1}\,.
\end{eqnarray*}

\begin{eqnarray*}
\Delta D_{min} 
 & \le & \sum_{j=1}^{C-1} (C+j-1) \frac{1}{2^{min}} 
              \left( \frac{1}{1+(j-1)/C} - \frac{1}{1+j/C} \right) \\
& = & \frac{C}{2^{min}} \cdot \sum_{j=1}^{C-1}  \frac{1}{C+j}\,.

\end{eqnarray*}

Let $K = 2^{min} / C^2 \in\{1,2\}$.
Then the density of the final powers-of-two Pinwheel instance $(g_1, g_2, \ldots, g_r)$ is at most

\begin{eqnarray} 
\lefteqn{\hspace{-4mm}D + \Delta D_{above} + \Delta D_{min}} \nonumber \\[1mm] 
  & \le & \frac{1+1/C}{1+\delta} + \frac{1}{2^{min}} \cdot \frac{C-1}{2C-1}
     + \frac{C}{2^{min}}  \cdot \sum_{j=1}^{C-1}  \frac{1}{C+j} \nonumber \\
   & = & \frac{1+1/C}{1+\delta} + \frac{1}{KC} \cdot \left(\frac{C-1}{C\cdot (2C-1)}
     + \sum_{j=1}^{C-1}  \frac{1}{C+j}\right) \lambdabel{kldf89a} \\[1mm]
   & = & \frac{1+1/C}{1+\delta} + \frac{1}{KC} \cdot \left(\frac{1}{C} - \frac{1}{2C-1}
     + \sum_{j=1}^{C-1}  \frac{1}{C+j}\right) \nonumber \\[1mm]

   & = & \frac{1+1/C}{1+\delta} + \frac{1}{KC} \cdot \sum_{j=C}^{2C-2}  \frac{1}{j} \nonumber \\

   & \le & \frac{1+1/C}{1+\delta} + \frac{1}{KC} \cdot \ln 2 \lambdabel{kldf89b} \\[1mm]

   & = & \frac{1}{1+\delta} + \frac{1}{C} \cdot \left(\frac{1}{1+\delta}+\frac{\ln 2}{K}\right) \nonumber \\[1mm]
   & \le & \frac{1}{1+\delta} + \frac{\sqrt{2K}}{3} \cdot \frac{\delta}{\sqrt{1+\delta}} \cdot \left(\frac{1}{1+\delta}+\frac{\ln 2}{K}\right) \lambdabel{chjk1a} \\[1mm]
   & \le & 1. \lambdabel{jkk34s}
\end{eqnarray}

To get Equality~\eqref{kldf89a}, use $2^{min} = K C^2$.
To get Inequality~\eqref{kldf89b}, use the known fact that for the harmonic numbers $H_k = 1 + 1/2 + 1/3 + 1/4 + ... + 1/k$, we have $H_k = \ln k  + \delta_k$, where $(\delta_k)$ is a sequence of positive numbers strictly monotonically decreasing. Hence, we have $H_{2k} - H_k = \ln 2 + \delta_{2k} - \delta_k < \ln 2$.

To get Inequality~\eqref{chjk1a}, use 

\[
C \cdot \sqrt{2K}  = \sqrt{2^{min+1}}                  
> \sqrt{f''_{1}} =  \sqrt{(1+\delta)\frac{H}{h_1}} 

= \frac{3\sqrt{1+\delta}}{\delta}\,. 
\]

Inequality~\eqref{jkk34s} follows from the fact that for $0 \le \delta \le 3$ and $K \in \{1,2\}$,
the function $f_K(\delta)$ in line~\eqref{chjk1a} is maximized for $\delta=0$.
To see this, substitute $\gamma \equiv\sqrt{\delta + 1}$ (so for $\delta$ increasing from $0$ to $3$, 
$\gamma$ increases from $1$ to $2$) to obtain
\begin{eqnarray}
 f_K(\delta) - 1 =  f_K(\gamma^2 -1) - 1
 & = & \frac{1}{\gamma^2} + \frac{\sqrt{2K}}{3} \cdot \frac{(\gamma^2 -1)}{\gamma} 
           \cdot \left(\frac{1}{\gamma^2}+\frac{\ln 2}{K}\right)-1  \nonumber\\
& = & \frac{\gamma^2 -1}{3\gamma^3} 
         \left( \frac{\sqrt{2}\ln 2}{\sqrt{K}} \gamma^2 -3\gamma +  {\sqrt{2K}} \right).
\lambdabel{opsds3a}
\end{eqnarray}
The quadratic in the parentheses in~\eqref{opsds3a}
has two distinct real roots
\[ \frac{3\pm \sqrt{9-8\ln 2}}{2\sqrt{2}\ln 2/\sqrt{K}}.
\]
For both $K\in \{1,2\}$, the smaller root $r_{K,1}$ is less than $1$
($r_{1,1} < r_{2,1} = 0.823...$)
and the larger root $r_{K,2}$ is greater than $2$
($r_{2,2} > r_{1,2} = 2.478...$).
This means that~\eqref{opsds3a} is equal to $0$ for $\gamma=1$ and negative for $\gamma\in (1,2]$,
or equivalently,  $f_K(\delta) - 1$ is equal to $0$ for $\delta = 0$ and negative for $\delta\in(0,3]$.

$\Box$\end{proof}

The discussion in Section~\ref{sec:BGT-Pinwheel} and Theorem~\ref{th:main} imply the following corollary.

\begin{corollary}
For Pinwheel instances $2 \le f_{1} \le f_{2}\le \ldots \le f_{n}$, 
the Main Algorithm applied to sequences $(1/f_{1}, 1/f_{2}, \ldots,  1/f_{n})$ is a 
Pinwheel scheduler with the guarantee density threshold $1 - 3/\sqrt{f_1}$. 
Thus each Pinwheel instance with density at most $1 - 3/\sqrt{f_1}$ is feasible. 
\end{corollary}

The Main Algorithm can be implemented so that its running time is $O(n\log n)$, 
assuming constant-time operations on real numbers, including the logarithm operation and 
rounding. 
Steps 1 and 2 take linear time (or $O(n\log n)$, if the input sequence is not provided in the sorted order).
In steps 3--5,
the non-empty groups  are maintained in a dictionary data structure, which can be created in $O(n\log n)$ time.

In steps 3 and 4, the groups are considered in the decreasing order (from the highest group in the highest layer).
In step 3, if two frequencies are paired by Observation 1, then the group to which the new frequency should be added 
can be found (or created, if empty) in $O(\log n)$ time. 
This can happen only $O(n)$ times, since each pairing reduces the number of frequencies, so step 3 
takes $O(n\log n)$ time.
In step 4, if $m$ frequencies are combined by Observation 2 into one new frequency $2^{min}/C$, 
then the required computation takes $O(m)$ time (in this case, 
no need to look for the group with frequencies $2^{min}/C$).
Thus step 4 takes $O(n)$ time.

In step 5, the groups are again considered in the decreasing order. 
For each group, frequencies are paired by Observation 1 or combined by Observation 2 (as above, all this computation 
takes $O(n\log n)$ time) and the remaining frequencies are appended to the next non-empty group in constant time.
Thus step 5 takes $O(n\log n)$ time.

Step 6, the computation of a cyclic schedule of the feasible powers-of-2 frequencies $(g_1, g_2, \ldots, g_r)$,
is done by the following algorithm from~\cite{holte_pinwheel:_1989}, which can be implemented to run in linear time,
assuming that the input sequence is sorted. 
Take two largest frequency values $g_{r-1}$ and $g_{r}$,
replace them with a new frequency $g' = 2g_{r-1}$ and compute a cyclic schedule for the new $(r-1)$-element 
sequence. 
To get a schedule for the original sequence $(g_1, g_2, \ldots, g_r)$, replace the occurrences of $g'$ with 
alternating occurrences of $g_{r-1}$ and $g_{r}$.
That is, if  $g'$ occurs at positions $p + k q$, for $k\ge 0$, then $g_{r-1}$ occurs at positions $p + 2k q$ and
 $g_{r}$ occurs at positions $p + (2k+1)q$, for $k\ge 0$.
 
During the computation in steps 3--5, the pairing and combining of frequencies is recorded in ordered trees 
as illustrated in Figure~\ref{f:CombineFreq}. The additional time required to create one such tree is linear in the 
size of the tree, so $O(n)$ time for creating all trees.
By traversing these trees, we can  
expand in $O(n)$ time the cyclic schedule of $(g_1, g_2, \ldots, g_r)$ to a cyclic schedule of $(f_1, f_2, \ldots, f_n)$.

The Main Algorithm computes the representation of a cyclic schedule in the form of pairs $(p_i, q_i)$, which enables
constant-time answers to queries: given the current step $T$, when will be the next step when a given element $b_i$ 
is serviced?
To generate the schedule step by step, taking $O(\log n)$ time per step, 
maintain a priority queue (e.g. as the heap data structure) 
with the pairs $(i, t_i)$, where $i = 1,2,\ldots, n$ and $t_i$ is the next step when element $b_i$ will be serviced.
 Initially the priority queue contains pairs $(i, p_i)$. 
 For the current step of the schedule, remove from the priority queue the pair $(i,t_i)$ with the smallest $t_i$, 
 schedule the element $b_i$, and insert to the priority queue the pair $(i, t_i+q_i)$.\footnote{
This works, if the cyclic schedule does not have gaps, and
the cyclic schedule computed in the Main Algorithm does not have gaps.
If the cyclic schedule may have gaps, then we should keep track of the current step $T$ and schedule $b_i$ only 
if $t_i = T$.}

\section{Continuous BGT}\lambdabel{sec:ContinuousBGT}

We consider now the continuous variant of the BGT problem.
Since this variant models scenarios when bamboos are spread over some geographical area,
we will now refer not only to bamboos $b_1, b_2, \ldots , b_n$
but also to the points $v_1, v_2, \ldots , v_n$
(in the implicit underlying space) where these bamboos are located.
We will denote by $V$ the set of these points.

Recall that input $I$
for the continuous BGT problem consists of the rates of growth of bamboos $(h_i:\: 1\le i \le n)$
and the travel times between bamboos $(t_{i,j}:\: 1\le i,j\le n)$.
We assume that $h_1 \geq h_2 \geq \ldots \geq h_n$, as before,
and normalize these rates, for convenience, so that $h_1+h_2+ \ldots +h_n = H= 1$
(this normalization is done without loss of generality, since only the relative heights of bamboos are relevant).
We assume that the travel distances form a metric on $V$.

For any $V' \subseteq V$,
the minimum growth rate among all points in $V'$ is denoted by $h_{\min}(V')$,
and the maximum growth rate among all points in $V'$ is denoted
by $h_{\max}(V')$. Let $h_{\min} = h_{\min}(V) = h_n$, and $h_{\max} = h_{\max}(V) = h_1$.

The diameter of the set $V$ is denoted by $D = D(V) = \max\{t_{i,j}:\: 1 \le i, j \le n\}$.
For any $V' \subseteq V$, ${\mbox{\it MST}}(V')$ denotes the minimum weight of a spanning tree on $V'$
(the travel times are the weights of the edges).
Recall that for an algorithm ${\cal{A}}$ and input $I$,
${\mbox{\it MH}}({\cal{A}}(I))$ denotes the maximum height that any bamboo ever reaches, if
trimming is done according to the schedule computed by ${\cal{A}}$,
and ${\mbox{\it OPT}}(I)$  is the optimal (minimal) maximum height of a bamboo over all schedules.

\subsection{Lower bounds and simple approximation based on discrete BGT}\lambdabel{sec:Continuous-LB}

We first show some simple lower bounds on the maximum height of a bamboo.
For notational brevity, we omit the explicit reference to the input $I$.
For example, the inequality ${\mbox{\it MH}}({\cal{A}}) \ge D h_{\max}$ in the lemma below
is to be understood as ${\mbox{\it MH}}({\cal{A}}(I)) \ge D(V(I)) \cdot h_{\max}(V(I))$, for each input instance $I$.

\begin{lemma}\lambdabel{LB1}
${\mbox{\it MH}}({\cal{A}}) \ge D h_{\max}$, for any algorithm ${\cal{A}}$.
\end{lemma}

\begin{proof}
The robot must visit another point $x$ in $V$ at distance at least $D/2$ from $v_1$.
When the robot comes back to $v_1$ after visiting $x$ (possibly via a number of other points in $V$),
the bamboo at $v_1$ has grown at least to the height of $D h_1 = D h_{\max}$.

$\Box$\end{proof}

\begin{lemma}\lambdabel{LB2}
${\mbox{\it MH}}({\cal{A}}) \ge h_{\min}(V') \cdot {\mbox{\it MST}}(V'),$ for any algorithm ${\cal{A}}$ and $V' \subseteq V$.
\end{lemma}

\begin{proof}
Let $v$ be the point in $V'$ visited last: all points in $V'\setminus\{v\}$ have been visited
at least once before the first visit to $v$.
The distance traveled until the first visit to $v$ is at least ${\mbox{\it MST}}(V')$,
so the bamboo at $v$ has grown to the height at least $h_v \cdot {\mbox{\it MST}}(V')\ge h_{\min}(V') \cdot {\mbox{\it MST}}(V')$.

$\Box$\end{proof}

One may ask how good are the schedules for continuous BGT which are computed taking into account only 
the growth rates, ignoring the travel times. If we use, for example, the schedules computed by 
the 2-approximation algorithm from Section~\ref{sec:DiscreteBGT-offline},
which guarantee that the maximum height of a bamboo does not grow above $2$
(recall that we normalize the growth rates, so $H = 1$), 
then there are at most $\lfloor 2/ h_i \rfloor - 1$
cutting actions
between two consecutive cuttings of bamboo $b_i$.
Otherwise bamboo $b_i$ would grow in discrete BGT to the height at least 
$h_i (\lfloor 2/ h_i \rfloor +1) > 2 = 2H$.
Thus in continuous BGT the time between two consecutive cuttings of 
bamboo $b_i$ is at most $D\lfloor 2/ h_i \rfloor$, so the height of this bamboo is never greater than 
$h_i D \lfloor 2/ h_i \rfloor \le 2D$.
Combining this with Lemma~\ref{LB1},
we conclude that the 2-approximation algorithm for discrete BGT 
is a $(2/h_{\max})$-approximation algorithm for continuous BGT.
In particular, this approach gives $\Theta(1)$-approximate algorithm for continuous BGT
for inputs with $h_1 = \Theta(1)$. 

To derive good approximation algorithms for other types of input,

we will use the lower bound from Lemma~\ref{LB2}.

\subsection{Approximation algorithms}\lambdabel{sec:ContinuousAlgo}

We present in this section three approximation algorithms for continuous BGT which
are based on computing spanning trees.
Algorithm 1 computes only one spanning tree of all points and the schedule for the robot 
is to traverse repeatedly an Euler tour of this tree. 
This simple algorithm ignores the growth rates of bamboos and computes a schedule of cutting
taking into account only the travel times between points.

Algorithms 2 and 3 group the bamboos according to the similarity of their growth rates 
and compute a separate spanning tree 
for each group. 
The robot moves from one tree to the next in the Round-Robin fashion.
At each spanning tree $T$, the robot walks along the Euler-tour of this tree for time~$D$ before moving 
to the next tree. When the robot eventually comes back to tree $T$, it resumes traversing 
the Euler tour of $T$
from the point when it last left this tree.
The growth rates of bamboos in the same spanning tree are within a factor of~2.
Algorithm 3 differs from Algorithm 2 by using spanning trees only for the first $\Theta(\log n)$ groups, which 
include bamboos with growth rates greater than $1/n^2$. 
The remaining bamboos, which all have low growth rates, are dealt with individually.

We describe our Algorithms 1, 2 and 3 in pseudocode
and give their approximation ratio in the theorems below.
The description of each algorithm consists of two parts: \emph{pre-processing} and \emph{walking}. 
We do not explicitly mention the actions of cutting/attending bamboos, assuming that 
whenever the robot passes a point in $V$\!, it cuts the bamboo growing at this point.

\begin{theorem}
Algorithm~1 is an $O({h_{\max}}/{h_{\min}})$-approximation algorithm for the continuous BGT problem.
\end{theorem}

\begin{proof}
Let ${\cal{A}}_1$ denote Algorithm 1.
Every point $v_i \in V$ is visited by ${\cal{A}}_1$ at least every $2 \cdot {\mbox{\it MST}}(V)$ time units.
Hence,
\begin{equation}
\lambdabel{eq:algo1a}
{\mbox{\it MH}}({\cal{A}}_1) = O(h_{\max}(V) \cdot {\mbox{\it MST}}(V)).
\end{equation}
According to Lemma~\ref{LB2},
\begin{equation}
\lambdabel{eq:algo1b}
{\mbox{\it OPT}} = \Omega(h_{\min}(V) \cdot {\mbox{\it MST}}(V)).
\end{equation}
Combining the two bounds (\ref{eq:algo1a}) and (\ref{eq:algo1b}),
it follows that Algorithm~1 is an $O({h_{\max}}/{h_{\min}})$-approximation algorithm for BGT.

$\Box$\end{proof}

\begin{theorem}
Algorithm~2 is an $O(\log({h_{\max}}/{h_{\min}}))$-approximation algorithm
for the continuous BGT problem.
\end{theorem}

\begin{proof}
For any $i \in \{1,2,\ldots,s\}$, consider any point $v \in V_i$.
The robot walks along one tree for  at most distance $2D$ and then covers at most distance $D$ to move to the next tree.
After a visit to point $v$, the robot comes back to tree $T_i$ at most 
$\left\lceil{2\cdot{\mbox{\it MST}}(V_i)}/{D}\right\rceil$ times before visiting $v$ again.
Therefore, recalling from the algorithm that there are at most 
$s = \lfloor\log_2({h_{\max}}/{h_{\min}})\rfloor+1$ trees,
the distance traveled between two consecutive visits to point $v$ is at most
\begin{eqnarray*} 
3Ds \left\lceil\frac{2\cdot{\mbox{\it MST}}(V_i)}{D}\right\rceil & \le & 3s (D + 2\cdot{\mbox{\it MST}}(V_i)).

\end{eqnarray*}
Hence, the height of the bamboo at $v$ is always 
\begin{equation}
\lambdabel{eq:algo2a}
O\left(h_{\max}(V_i) \cdot \log\left(\frac{h_{\max}}{h_{\min}}\right) \cdot \max\{D,{\mbox{\it MST}}(V_i)\}\right).
\end{equation}
On the other hand, using Lemmas~\ref{LB1} and \ref{LB2}, we obtain
\begin{equation}
\lambdabel{eq:algo2b}
{\mbox{\it OPT}} \; \ge \; h_{\min}(V_i) \cdot \max\{D,{\mbox{\it MST}}(V_i)\}.
\end{equation}

Combining the two bounds (\ref{eq:algo2a}) and (\ref{eq:algo2b}), and observing that 
$h_{\max}(V_i) \leq 2\cdot h_{\min}(V_i)$,
we obtain that the height of the bamboo at $v$ 
is always $O({\mbox{\it OPT}} \cdot \log({h_{\max}}/{h_{\min}}))$, so
Algorithm~2 is an $O(\log({h_{\max}}/{h_{\min}}))$-approximation algorithm for BGT.

$\Box$\end{proof}

\begin{theorem}
Algorithm~3 is an $O(\log n)$-approximation algorithm for the continuous BGT problem.
\end{theorem}

\begin{proof}
Each round of Algorithm~3, that is, each iteration of the repeat loop, is a cycle over all $s = \Theta(\log n)$ trees 
and a visit to one point in the set $V_0$.
Consider any point $v \in V_i$, for any $i \in \{1,2,\ldots,s\}$.
The distance traveled between two consecutive visits of $v$ is at most
\begin{eqnarray*}
(3Ds + D)\left\lceil\frac{2\cdot{\mbox{\it MST}}(V_i)}{D}\right\rceil & \le & (3s+1) (D + 2\cdot{\mbox{\it MST}}(V_i)) \\
& = & O(\log n \cdot \max\{D,{\mbox{\it MST}}(V_i)\}).
\end{eqnarray*}
Hence, the height of the bamboo at $v$ is always
\begin{equation}
\lambdabel{eq:algo3a}
O(h_{\max}(V_i) \cdot \log n \cdot \max\{D,{\mbox{\it MST}}(V_i)\}). \nonumber
\end{equation}
Using the lower bound~\eqref{eq:algo2b} on ${\mbox{\it OPT}}$

and the fact that  $h_{\max}(V_i) \le 2 \cdot h_{\min}(V_i)$, we conclude that 
the height of the bamboo at $v$ is always $O({\mbox{\it OPT}}\cdot\log n)$.

Consider now a point $v \in V_0$.
The distance traveled between two consecutive visits of $v$ is at most
$$(3Ds + D)|V_0| \; = \; O(n \cdot D \cdot \log n).$$
Hence, the height of the bamboo at $v$ is always
\begin{equation}
\lambdabel{eq:algo3c}
O(h_{\max}(V_0) \cdot n \cdot D \cdot \log n)
= O(n^{-2} \cdot n \cdot D \cdot \log n)
= O( h_{\max} \cdot D \cdot \log n). \nonumber
\end{equation}
This and Lemma~\ref{LB1} imply that the height of the bamboo at $v$ is always 
$O({\mbox{\it OPT}} \cdot \log n)$.
Thus Algorithm~3 is an $O(\log n)$-approximation algorithm for BGT.

$\Box$\end{proof}

Note that the pre-processing in all Algorithms~1, 2 and 3 is dominated by the minimum-spanning tree computation,
which can be implemented in $O(n^2)$ time (e.g.~by using Prim's algorithm \cite{Prim57}). 
Then the running time to produce the schedule (the consecutive steps of the schedule) is constant per one step of the schedule.

\subsection{How tight are the upper and lower bounds?}

Our $O(\log n)$-approximation algorithm for the continuous BGT (Algorithm~3)
can return schedules which are worse than the optimal schedules by 
a factor of $\Theta(\log n)$. 
For example, consider the input which consists of two sets $V'$ and $V''$ of $n/2$ points each such that 
in each set the points are very close to each other (with the total distance to visit all points in this set  less than $D$),
but the sets are at distance greater than $D/2$ from each other. 
The rates of growth in set $V'$ include the $\Theta(\log n)$ values $1/4, 1/8, \ldots, 1/2^i, \ldots, 1/n$,
and the same rates are in set $V''$.
For this input instance the value of the optimal schedule is $\Theta(D)$: visit all points in $V'$, then all points in $V''$
(for the total distance $\Theta(D)$),
and repeat.
The schedule computed by Algorithm~3 uses $\Theta(\log n)$ trees and makes the robot traverse each tree for 
a distance at least $D$ before returning to the bamboo with the highest rate of growth of $1/4$. 
Thus this bamboo
grows to the height $\Theta(D\log n)$, which is a factor of $\Theta(\log n)$ worse than the optimum.

The approximation bounds which we presented 
in Section~\ref{sec:ContinuousAlgo} are derived 
by comparing the upper bounds on the maximum bamboo heights guaranteed by the algorithms
with the lower bounds shown in Section~\ref{sec:Continuous-LB}.
We show now a class of instances, for which
any schedule leads to bamboo heights greater than our lower bounds
by a $\Theta(\log n)$  factor.
Thus for these input instances our general lower bounds turn out to be weak,
while our $O(\log n)$-approximation algorithm computes in fact constant approximation
schedules.
To improve the approximation ratio of algorithms for the continuous BGT to $o(\log n)$,
one will therefore require both:
new algorithmic techniques as well as stronger lower bounds. 

We consider the following input $V^*$ for the continuous BGT problem.
The $n$ points in $V^*$ are placed on the Euclidean plane within a unit-radius circle.
The points lie evenly spaced along the spiral inside this circle, which starts at a point $A$ at distance $1/2$
from the center of the circle and swirls outward creating rings separated by distance $d_2 = n^{-1/3}$;
see Figure~\ref{fig:spiral}, but note that the drawing is not to scale.
The first point in $V^*$ is at $A$
and the distance between two consecutive points in $V^*$ along the spiral is $d_1 = n^{-2/3}$.
Thus the length of the spiral occupied by the points in $V^*$ is equal to $n^{1/3}$, so all points
are indeed inside the circle.
(The length of the part of the spiral which is within the circle is at least $(1/2)\pi n^{1/3}$,
since there are $n^{1/3}/2$ rings and each ring has length at least $\pi$.)

\begin{figure}
\caption{Example of a spiral input.
\lambdabel{fig:spiral}
\end{figure}

The points in $V^*$ are grouped into subsets $G_1, G_2, \ldots, G_{(\log n)/3}$ and $G'$
of consecutive points along the spiral, starting from position $A$.
(For convenience, we assume that $(\log n)/3$ is an integer.)
The first two groups $G_0$ and $G_1$ are indicated in Figure~\ref{fig:spiral}.
For $i =1, 2, \ldots, (\log n)/3$, the size of group $G_i$ is
$n/2^{i}$
and each point in $G_i$ has the same growth rate $h_i = (3 -
$\Box$silon) 2^i/(n\log n)$,
where $0 < 
$\Box$silon = o(1)$.
The last group $G'$ contains the remaining $o(n)$ points in $V^*$ and the growth rate of each point in $G'$
is equal to $h' = 1/n^{4/3} = h_{\min}(V^*)$.
The exact value of $
$\Box$silon = o(1)$ is such that all growth rates sum up to $1$.

The diameter of $V^*$ is $1 \le D \le 2$ and 
$h_{\max}(V^*) = h_{(\log n)/3} = \Theta(1/(n^{2/3}\log n))$,
so Lemma~\ref{LB1} gives the lower bound of $\Omega(1/(n^{2/3}\log n))$ on the optimal solution.
We check now what lower bounds we can get from Lemma~\ref{LB2}.
The MST of this set of points $V^*$ is obtained by following the spiral and the weight of this MST is
equal to $nd_1 = n^{1/3}$, giving the lower bound of $h_{\min}(V^*) \cdot {\mbox{\it MST}}(V^*) = 1/n$.
For each $i = 1,2, \ldots, (\log n)/3$, 
the weight of the MST of the set of points $V' = \bigcup_{j = i}^{(\log n)/3} G_j$,
which is the subset of all points in $V^*$ with growth rates at least $h_i$,
is equal to
$d_1\left|\bigcup_{j = i}^{(\log n)/3} G_j\right| = \Theta(d_1 |G_i|) = \Theta(n^{1/3}/2^i)$.
This gives the lower bound of $h_i \cdot {\mbox{\it MST}}(V') = \Omega(1/(n^{2/3}\log n))$.
This is the best lower bound which we can obtain from Lemma~\ref{LB2}, 
since we maximize $h_{\min}(V') \cdot {\mbox{\it MST}}(V')$ by including in $V'$ \emph{all} 
points with growth rates at least $h_{\min}(V')$.
Thus Lemmas~\ref{LB1} and~\ref{LB2} give for this input instance the lower bound
$\Omega(1/(n^{2/3}\log n))$.

The $O(\log n)$-approximation Algorithm 3 gives the schedule for $V^*$ with the maximum
bamboo height $\Theta(1/n^{2/3})$, which is a $\log n$ factor above our lower bounds.
Indeed, observe that the sets $V_i$, $i \ge 0$ defined in Algorithm~3 coincide
with the sets $G'$ and $G_i$, for $i = 1,2, \ldots, (\log n)/3$.
This means that a bamboo in set $G_i$ grows up to the height of 
$\Theta(h_i D \log n \lceil{\mbox{\it MST}}(G_i)/D\rceil) = \Theta(1/n^{2/3})$.
We show next that for this input any possible schedule produces bamboos of height $\Omega(1/n^{1/3})$.

\begin{lemma}
For each schedule for the input $V^*$, there must be a bamboo which grows to the
height $d_1/2 = \Omega(1/n^{2/3})$.
\end{lemma}

\begin{proof}
Assume that there is a schedule
such that the height of each bamboo in $\bigcup_{i=1}^{(\log n)/3} G_i$ is always at most
$d_1/2$.
In such a schedule, each point in each set $G_i$ is serviced after at most distance
$(d_1/2) \cdot (n\log n)/((3-
$\Box$silon)2^i)\le d_1 \cdot (n\log n)/2^{i+2}$.
Since the distance between each two points in $V^*$ is at least $d_1$, the growth rate of
each point in $G_i$ in this schedule must be at least  $2^{i+2} /(n \log n)$.
Thus the sum of the growth rates of all points in $\bigcup G_i$ in this schedule is at least
\[ \sum_{i = 1}^{(\log n)/3} \frac{2^{i+2}}{n\log n} \cdot \frac{n}{2^i} = 4/3,
\]
which is a contradiction since the growth rates of the points
in any valid schedule must sum up to at most $1$.
This contradiction implies that in each valid schedule there is a bamboo which
grows higher  than $d_1/2$.

$\Box$\end{proof}

\section{Open questions}
\lambdabel{sec:conclusion}

There are several interesting open questions about approximation algorithms for the BGT problems.

For discrete BGT, we still do not know the exact worst-case approximation ratios
of simple strategies such as $\mbox{Reduce-Max}$ and $\mbox{Reduce-Fastest}$.

Assuming the growth rates are 
normalized to $H=1$,
the best known upper bound 
on the maximum height of a bamboo
under the $\mbox{Reduce-Fastest}$ strategy
is $2.62$, and the only known constant
upper bound for $\mbox{Reduce-Max}$ is $9$ --
both bounds shown recently by 
Bil{\`{o}} {\em et al.}~\cite{BGLPS21}.
For both strategies, there are simple examples showing that bamboos can reach heights arbitrarily close to $2$, but 
we do not know of any examples when the heights would go above~$2$. 

Other set of questions are about improving approximation ratios of offline 
Pinwheel-based algorithms. 
Van Ee~\cite{Ee21} has recently improved on the simple 2-approximation described in 
Section~\ref{sec:DiscreteBGT-offline}, 
designing a $12/7$-approximation algorithm. 
Can this bound be further improved?
Another question is whether the $1+O(\sqrt{h_1/H})$ approximation ratio of our main algorithm for discrete 
BGT can be improved. Can we achieve an approximation ratio of $1+O({h_1/H})$, or 
even just $1+o({\sqrt{h_1/H}})$?

For continuous BGT, we do not know whether our Algorithm 3, or any other algorithm, achieves
an approximation ratio of  $o(\log n)$. 
The two special cases of continuous BGT -- discrete BGT and the metric TSP -- have both constant-ratio
polynomial-time approximation algorithms, not giving any indication why we should not expect the same for the 
more general problem. 

Note that a constant approximation for the path was given in~\cite{DBLP:conf/sofsem/ChuangpishitCGG18},
and very recently at IWOCA 2020 (best paper) a PTAS was presented by Peter Damaschke~\cite{DBLP:conf/iwoca/Damaschke20}.

\end{document}