Approximation Algorithms for Replenishment
Problems with Fixed Turnover Times
Thomas Bosman1 , Martijn van Ee1 , Yang Jiao2 , Alberto Marchetti-Spaccamela3 ,
R. Ravi2 , and Leen Stougie1,4

arXiv:1712.05218v1 [] 14 Dec 2017

1

Vrije Universiteit, Amsterdam, The Netherlands
{thomas.bosman,m.van.ee,l.stougie}@vu.nl
2
Tepper School of Business, Carnegie Mellon University, Pittsburgh, PA, USA
{ravi,yangjiao}@andrew.cmu.edu
3
Sapienza University of Rome, Rome, Italy
alberto@dis.uniroma1.it
4
Centrum voor Wiskunde en Informatica (CWI), Amsterdam, The Netherlands
l.stougie@cwi.nl

Abstract. We introduce and study a class of optimization problems we
coin replenishment problems with fixed turnover times: a very natural
model that has received little attention in the literature. Nodes with
capacity for storing a certain commodity are located at various places; at
each node the commodity depletes within a certain time, the turnover time,
which is constant but can vary between locations. Nodes should never
run empty, and to prevent this we may schedule nodes for replenishment
every day. The natural feature that makes this problem interesting is that
we may schedule a replenishment (well) before a node becomes empty,
but then the next replenishment will be due earlier also. This added
workload needs to be balanced against the cost of routing vehicles to do
the replenishments. In this paper, we focus on the aspect of minimizing
routing costs. However, the framework of recurring tasks, in which the
next job of a task must be done within a fixed amount of time after the
previous one is much more general and gives an adequate model for many
practical situations.
Note that our problem has an infinite time horizon. However, it can be
fully characterized by a compact input, containing only the location of
each store and a turnover time. This makes determining its computational
complexity highly challenging and indeed it remains essentially unresolved.
We study the problem for two objectives: min-avg minimizes the average
tour length and min-max minimizes the maximum tour length over all
days. For min-max we derive a logarithmic factor approximation for
the problem on general metrics and a 6-approximation for the problem
on trees, for which we have a proof of NP-hardness. For min-avg we
present a logarithmic approximation on general metrics, 2-approximation
for trees, and a pseudopolynomial time algorithm for the line. Many
intriguing problems remain open.

1

Introduction

Imagine the following particular inventory-routing problem. A set of automatic
vendor machines are spread over a country or a city. They have a certain turnover
time: the number of days in which a full machine will be sold out. Replenishment
is done by vehicles. Let us assume that turnover times are machine dependent
but not time dependent, and that it is highly undesirable to have an empty
machine. However, the holding costs of the machine are negligible, so that we
will always fill the machine to capacity. There is nothing against replenishing a
machine before it has become empty, but then the next replenishment will due
earlier as well. That is, the deadline of the next replenishment is always within
the turnover time after the last replenishment. Equivalently, in any consecutive
number of days equal to the turnover time, at least one replenishment has to
take place. Replenishing a machine earlier to combine it with the replenishment
of another machine that is due earlier may lead to cost savings. The feature
that makes this problem so special w.r.t. existing literature, is that it can be
compactly modeled by only specifying for every machine its location and the
turnover time. The feature is very natural but has hardly been studied in the
existing literature. There are intriguing basic open complexity questions, and
some highly non-trivial results.
The motivation for studying this problem comes linea recta from a business
project for the replenishment of ATMs in the Netherlands, in which some of
the co-authors are involved. The replenishment of the ATMs of all the large
banks in the Netherlands has been outsourced to a single company: Geld Service
Nederland. Of course the real-life ATM replenishment problem is not as stylized
as described above; the turnover time is not strictly the same over time but
subject to variability, there are restrictions on the routes for the vehicles, etc. But
the feature that is least understood in the ATM-problem is exactly the problem
of how to deal with the trade-off between replenishing an ATM earlier than its
due date leading to a higher frequency of replenishments and the savings on
vehicle routing costs.
Formally, an instance of the problem that we study in this paper, which we
baptize the replenishment problem with fixed turnover times (rftt),
consists of a pair (G, τ ), where G = (V ∪ {s}, E, c) is a weighted graph with a
designated depot vertex s and weights on the edges c : E → R+ , and turnover
times τ ∈ N|V | , indicating that vj ∈ V should be visited at least once in every
interval of τj days.
A solution consists, for each day k, of a tour Tk in G starting in and returning
to the
depot s and visiting a subset of the vertices Jk ⊆ V . It is feasible if
St+τ
j
vj ∈ k=t+1
Jk , ∀t and ∀vj ∈ V . We will focus on solutions that repeat themselves
after a finite amount of time, that is, in which (Tk , ..., Tk+` ) = (Tk+`+1 , ..., Tk+2` )
for some `, and all k. Since all turnover times are finite, this is no real restriction.
We consider two versions of rftt. In the first version, called min-avg, the
goal is to find a feasible solution that minimizes the average tour length. In
the min-max problem, we want to find a feasible solution that minimizes the
maximum tour length over all days.

We emphasize that the particular feature of this model, that jobs or visits to
clients recur and need to be done within each job-specific consecutive time interval
occurs naturally in many problem settings. It allows any job of a recurring task
to be done before its deadline, but then the next job of the task comes earlier
and hence its deadline. This is a feature that, despite its natural applicability,
has hardly been studied in the literature from a theoretical point of view.
Related work. As mentioned before, our problem can be seen as a special case of
the Inventory Routing Problem (IRP) [8]. Here, clients (vertices) have their
own storage with a certain capacity and for each day a demand is specified. The
clients pay holding cost over their inventory. However, omitting inventory cost,
we can interpret our problem as such an inventory routing problem in which
the demand at any given location is the same every day, leading to a very small
input description of our problem consisting only of a location and a turnover
time (storage capacity divided by daily demand), which makes it incomparable
to the inventory routing problem from a complexity point of view. Indeed it is
unclear if the decision version of our problem is in NP or in co-NP.
Another closely related problem is the Periodic Latency Problem [9],
which features the recurring visits requirement of rftt. We are given recurrence
length qi for each client i and travel distances between clients. Client i is considered
served if it is visited every qi time units. The server does not return to the depot at
the end of each time unit (e.g. day), but keeps moving continuously between clients
at uniform speed. Another difference between Periodic Latency Problem
and rftt is the objective function. Coene et. al. [9] study two versions of the
problem: one that maximizes the number of served clients by one server, and one
that minimizes the number of servers needed to serve all clients. They resolve the
complexity of these problems on lines, circles, stars, trees, and general metrics.
A problem that does share the compact input size and is in fact a very special
case of our problem is known under the guise of Pinwheel Scheduling. It
has been introduced to model the scheduling of a ground station to receive
information from a set of satellites without data loss. In terms of our problem no
more than one vertex can be replenished per day and all distances to the depot
are the same; the interesting question here is if there exists a feasible schedule for
replenishing the vertices. Formally, a set of jobs {1, ..., n} with periods p1 , ..., pn
is given, and the question is whether there exists a schedule σ : N → {1, .., n}
St+pj
such that j ∈ k=t+1
σk , ∀t ≥ 0 and ∀j.
Pinwheel Scheduling was introduced by Holte et al. [18], who showed that
it is contained in PSPACE. The problem is in NP if the schedule σ is restricted
to one in which for each job the time between two consecutive executions remains
constant throughout
the schedule. In particular this holds for instances with
P
density ρ = j 1/pj = 1 [18]. They also observed that the problem is easily
solvable when ρ ≤ 1 and the periods are harmonic, i.e. pi is a divisor of pj or
vice versa for all i and j. As a corollary, every instance with ρ ≤ 12 is feasible.
Chan and Chin [7] improved the latter result by giving an algorithm that
produces a feasible schedule for Pinwheel Scheduling whenever ρ ≤ 23 . In [6],
7
they improved this factor to 10
. Later, Fishburn and Lagarias [14] showed that

every instance with ρ ≤ 34 has a feasible schedule. All these papers work towards
the conjecture that there is a feasible schedule if ρ ≤ 65 . That this bound is tight
can be seen by the instance with p1 = 2, p2 = 3 and p3 = M , with M large. This
1
.
instance cannot be scheduled, but has a density of 56 + M
The complexity of Pinwheel Scheduling has been open since it was
introduced. It was only recently shown by Jacobs and Longo [19] that there is
no pseudopolynomial time algorithm solving the problem unless SAT has an
exact algorithm running in expected time nO(log n log log n) , implying for example
that the randomized exponential time hypothesis fails to hold [5,10]. Since the
latter is unlikely, one could conclude that Pinwheel Scheduling is not solvable
in pseudopolynomial time. It remains open whether the problem is PSPACEcomplete.
Similar to Pinwheel Scheduling, the k-server Periodic Maintenance
Problem [21,2,11] has n jobs, each with a specified periodicity and a processing
time. Each server may serve at most one job per time unit. However, job i is
required to be served exactly every mi days apart rather than within every mi
days. The case k = 1, cj = 1 for all j is analogous to Pinwheel Scheduling,
except for the exact periodicity constraint. For any k ≥ 1, Mok et. al. [21] have
shown it is NP-complete in the strong sense. For the special case when mi are
multiples of each other or when there are at most 2 different periodicities, they
have shown it is in P. It was shown that even in the case of a single server and
cj = 1 for all j the problem remains coNP-hard [3].
d Other related problems with a compact input representation include realtime scheduling of sporadic tasks [1,4], where we are given a set of recurrent tasks.
On a single machine, EDF (Earliest Deadline First) is optimal. However, we
remark that the complexity of deciding whether a given set of tasks is feasible has
been open for a long time and only recently proved showing that it is coNP-hard
to decide whether a task system is feasible on a single processor even if the
utilization is bounded [12].
Another related problem is the Bamboo Garden Trimming Problem
introduced by Gasieniec et. al. [17]. There are n bamboos, each having a given
growth rate, which may be viewed as inducing a periodicity. On each day, a robot
may trim at most one bamboo back to height 0. The goal is to minimize the
maximum height of the bamboos. Gasieniec et. al. provide a 4-approximation for
the general case and a 2-approximation for balanced growth rates.
This paper. We investigate the computational complexity of both the min-max
and the min-avg version of rftt. Mostly we will relate their complexity to
the complexity of Pinwheel Scheduling. Some interesting inapproximability
results follow from this relation. After that, we will start with some special cases.
In Section 3, we give our most remarkable result, a constant factor approximation
for min-max on a tree, next to a less remarkable constant approximation for
the min-avg version on the tree. In the same section, we show for min-avg
that the problem can be solved to optimality in pseudopolynomial time on line
metrics. Finally, in Section 4, we present logarithmic factor approximations for
both problem versions on general metrics.

2

Complexity

In this section, we investigate the computational complexity for both objectives.
Since our problem requires finding a shortest tour visiting some subset of vertices
for every day, it is at least as hard as the Traveling Salesman Problem
(tsp). However it is also interesting to note that the problems are at least as hard
as Pinwheel Scheduling as well. For the min-max objective there is a direct
reduction showing that a factor 2 approximation is at least as hard as Pinwheel
Scheduling: construct an unweighted star with the depot at the center and
each leaf corresponding to a job in the pinwheel instance. This instance has value
2 only if there exists a pinwheel schedule and at least 4 otherwise.
For the min-avg rftt the reduction is a bit more involved, and given in the
appendix.
Theorem 1. On series-parallel graphs, min-avg rftt is at least as hard as
Pinwheel scheduling.
We note that this hardness result is incomparable to the tsp reduction. Pinwheel
is neither known to be NP-hard nor in NP, although it is conjectured to be
PSPACE-complete.
Lastly, as Theorem 2 shows, the min-max rftt remains hard even on star
graphs (where TSP is trivial). A reduction can be found in the appendix.
Theorem 2. min-max rftt is NP-hard on star graphs.

3

Approximation on trees

In this section we give a 2-approximation for min-avg and a 6-approximation
for min-max on trees.
We start out with a simplifying result, which will also be of use in the next
sections. The proof of Lemma 1, which is not hard to derive, can be found in the
appendix.
Lemma 1. Given an instance (G, τ ) of rftt, let τ 0 be found by rounding every
turnover time in τ down to a power of 2. Then OP T (G, τ 0 ) ≤ 2OP T (G, τ ) for
both min-avg and min-max objectives.
In the remainder we assume w.l.o.g. that G is rooted at s and that turnover
times are increasing on any path from the depot to a leaf node in G. Furthermore,
for an edge e in E we define D(e) to be the set of vertices that are a descendant
of e. We also need the following definition.
Definition 1 (tt-weight of an edge). For any edge in G we define:
q(e) = min τj .
j∈D(e)

We call this quantity the tt-weight (turnover time-weight) of e.

This definition allows us to express the lowerbound in Lemma 2.
Lemma 2 (tt-weighted tree). For an instance (G, τ ) of the rftt on trees it
holds that the average tour length is at least:
L(G, τ ) := 2

X c(e)
.
q(e)

e∈E

2
Proof. This follows immediately from the fact that q(e)
lower bounds the number
of times edge e must be traversed on average in any feasible solution.

Since the maximum tour length is at least the average tour length, Lemma 2 also
provides a lower bound for the min-max objective.
An approximation for min-avg rftt is thus found by rounding all turnover
times to powers of 2 and then visit each client j on every day that is a multiple
of τj . Since in that case the lower bound of Lemma 2 is exactly attained on the
rounded instance, Lemma 1 implies the following theorem.
Theorem 3. There is a 2-approximation for min-avg rftt on trees.
3.1

MIN-MAX

We will now show that we can achieve a 6-approximation for min-max rftt on
trees by providing a 3-approximation algorithm if all turnover times are powers
of 2 and then applying Lemma 1.
The main idea is to take a TSP-tour and recursively split it to obtain a schedule
for the clients with increasing turnover times. During the splitting process, we
assign each client j on that tour to a congruence classes āτj = {k ∈ N|k ≡ a
(mod τj )} for some a ≤ τj , to indicate we want to visit j on each day in āτj .
Similarly, we distribute all edges e to a congruence class āq(e) . We do this ensuring
that on any given day, we can create a tour through all clients associated with
that day, using the edges associated with that day plus a small set of extra edges.
Let us define some further notation. For a given congruence class ām ⊆ N, we
denote g(ām ) ⊆ V the set of vertices and f (ām ) ⊆ E the set of edges assigned
to that class. Note that ām and (a + m)m define the same congruence class, so
f (ām ) = f ((a + m)m ). Then, for any k ∈ N we have that Jk , the set of clients
we need to visit on day k, is
[
Jk =
g(ām ).
m∈N,a≤m|k∈ām

The assignment of vertices and edges to classes is guided by the recursive
splitting of a TSP-tour in G. The full procedure for constructing f (·) and g(·) is
shown in Algorithm 1. The algorithm is initially called with d, a TSP-tour visiting
all vertices in G, and a = m = 1 and will determine the set of vertices to be
visited on every day (i.e., those congruent to ā1 ). Then the first (second) recursive
call determines the sets of vertices with turnover time 2 that will be visited on odd

Algorithm 1 Algorithm for recursively constructing f (·) and g(·)
function RecurseTreeSchedule(d, a, m)
Require: d, a connected sequence of edges in G, powers of 2 turnover times τ ; a, m,
integers
if d 6= ∅ then
f (ām ) = {e ∈ d | q(e) = m}
g(ām ) = {j ∈ V (d) | τj = m}
P
P
c(di )
c(di )
k = maxk0 s.t. i∈[k0 −1]|q(di )>m q(d
≤ 12 i∈[n]|q(di )>m q(d
i)
i)
d1 = (d1 , . . . , dk−1 )
d2 = (dk+1 , . . . , dn )
RecurseTreeSchedule(d1 , a, 2m), RecurseTreeSchedule(d2 , a + m, 2m)
end if
end function

(even) days. Analougously, RecurseTreeSchedule(d1 , a, m) will return the
set of vertices with turnover time m to be visited on days in the congruence class
ām and the two recursive calls will return the set of vertices with turnover time
2m that are visited on days a, a + 2m, a + 4m, . . . and a + m, a + 3m, a + 5m, . . .,
respectively.
In the remainder we assume that any call to f (·) and g(·) returns the empty
set for any argument that is not explicitly handled in Algorithm 1. Note that we
use the notation V (A) to denote the vertices incident to edges in A ⊆ E.
Lemma 3. After Algorithm 1 terminates, each vertex j appears in some set
g(āτj ) for some a.
Proof. Note that d1 ∩ d2 = ∅ and that |d1 ∪ d2 | = |d| − 1; since d is a connected
set of edges then in each call to RecurseTreeSchedule, V (d1 )∪V (d2 ) = V (d).
Therefore no vertex is skipped in the construction of g(·).
S In order to find a tour on day k through the vertices in Jk we use edges in
h=1,2,...,m f (āh ); as we already observed this set of edges does not necessarily
connect vertices in g(ām ) to the depot. The next lemma shows that a tree
that connects all vertices in g(ām ) to the root can be found by considering
∪h=1,2,...,m f (āh ) and adding a shortest path from some vertex in g(ām ) to the
depot.
Lemma 4. Let a, m be such that f (ām ) is nonempty. Let P be the set of edges
on the shortest path connecting some arbitrary edge in f (ām ) to the root of G.
Then the following edge set forms a connected component:
[
T (ām ) := P ∪ (
f (āh )).
h=1,2,...,m

Moreover, T (ām ) spans

S

h=1,2,...,m/2,m

g(āh ).

Proof. To prove our first claim, we first show that for k ≤ m, f (āk ) either induces
at most one connected component, or each component it induces is incident to a

S
component induced by h=1,2,..,k/2 f (āh ). Then, we will show that if f (āk ) induces
S
at most one connected component, it is incident to P ∪ ( h=1,2,..,k/2 f (āh )).
Suppose f (āk ) does not induce at most one component. Note that f (āk ) is
the subset of edges in some connected edge sequence d through G that have
tt-weight k. But by the way tt-weight is defined and the fact that G is a tree,
a simple path connecting disjoint edges with tt-weight k, can only consist of
edges with tt-weight at most k. So every two components in f (āk ) are connected
through a path of edges with tt-weight of at most k. Moreover since the sequence
d used to construct f (āk ) is a subset of the sequence usedSto construct f (āk/2 ),
by induction these connecting paths must be contained in h=1,2,...,k/2 f (āh ), as
required.
Next we show that for any
S k ≤ m such that f (āk ) 6= ∅, if f (āk ) is not incident
to P then it is incident to h=1,...,k/2 f (āh ).
Let d be the sequence that was used to construct f (āk ). Since d contains all
edges in f (ām ) and P contains at least one such edge, there exists a minimal path
Q that contains some edge e in f (āk ) such that Q is connected to P . Moreover
since Q is minimal and P contains the root, e must be the edge furthest away
from the root on Q. This implies that all edges on Q have tt-weight k or less.
Now suppose that Q contains Sedges with tt-weight strictly less than k. Then
those edges are necessarily in h=1,...,k/2 f (āh ) and therefore f (āk ) is incident
to that set. If not then Q is strictly contained in f (āk ) and therefore f (āk ) is
connected to P .
The first claim S
of our lemma now follows by induction. P ∪ f (ā1 ) is clearly
connected. If P ∪ h=1,2,...,k/2 f (āh ) is connected, we get that f (āk ) is either
S
empty or is connected to P or to h=1,2,...,k/2 f (āh ), and the result follows.
To prove our second claim,
S suppose that for some k and j ∈ g(āk ) it holds that
no edge incident to j, is in h=1,2,...,k f (āh ). We will show that that j appears
on P , from which our claim immediately follows.
Let d be the sequence used to construct g(āk ). The edge e incident to j that
is closest to the S
root, satisfies q(e) ≤ k. So, it cannot be in d otherwise it would
be contained in h=1,2,...,k f (āh ). But this implies that e cuts off every edge in d
from the root, and therefore e appears on P , as claimed, concluding the proof.
The next lemma allows us to bound the cost of edges included in f (āh ).
Lemma 5. During each (recursive) call to RecurseTreeSchedule, it holds
that
m/2
X
X
c(e) X
m
+
c(e) ≤ L(G, τ ).
q(e)
e∈d|q(e)≥m

h=1 e∈f (āh )|q(e)=h

Proof. The proof is by induction on m. Since we initially call the algorithm with
d a TSP-tour in G, which visits each edge twice, it clearly holds for m = 1.
Now for m > 1, suppose it holds for all smaller m. Without loss of generality,
suppose we have a call to the function with input d1 , a, m, such that d, a, m/2
are the input parameters for its parent in the call stack.

X

m

e∈d1 |q(e)≥m

X

=

m

e∈d1 |q(e)≥m

X

≤

e∈d|q(e)≥m

c(e)
+
q(e)

m c(e)
+
2 q(e)

X

≤

c(e)
+
q(e)

e∈d|q(e)≥m/2

X

X

c(e)

h=1,2,..., m
2 e∈f (āh )|q(e)=h

X
e∈f (ām/2 )|q(e)=m/2

X
e∈f (ām/2 )|q(e)=m/2

m c(e)
+
2 q(e)

X

m c(e)
+
2 q(e)
m c(e)
+
2 q(e)

X

X

X

c(e)

h=1,2,..., m
4 e∈f (āh )|q(e)=h

X

X

c(e)

h=1,2,..., m
4 e∈f (āh )|q(e)=h

c(e) ≤ L(G, τ )

h=1,2,..., m
4 e∈f (āh )|q(e)=h

For the first equality, we split the second sum into an h = m/2 part and an
h = 1, . . . , m/4 part. In the first inequality we used the way d1 and d2 are
determined in Algorithm 1, in the second inequality we used that f (ām ) ⊆ d and
in the last inequality we used the inductive hypothesis, concluding the proof.
We are now ready for the main theorem.
Theorem 4. There is a 6-approximation for min-max rftt on trees.
Proof. We first round all turnover times down to powers of 2, which loses a factor
of 2 in the optimal solution. We then use Algorithm 1 to construct f (·) and g(·)
thus determining the set of vertices Jk to be visited on day k. By Lemma 3 this
defines a feasible schedule.
If we then take T (k̄τmax ) as in Lemma 4, we get a tree that spans Jk . Moreover
the weight of T (k̄τmax ) is at most 32 OP T : the contribution of P is at most 12 OP T ,
since we need to reach
S any client at least on some day (and drive back), while
the contribution of h=1,..τmax f (k̄h ) is at most L(G, τ ) ≤ OP T , which can be
seen by applying Lemma 5 for m = 2τmax . Lastly, since we need a tour around
T (k̄τmax ), we lose another factor 2. This gives the approximation factor of 6.
It remains to show that Algorithm 1 runs in polynomial time, and that
we can find a polynomial representation for the schedule. For the first claim,
note that in each recursive call to the algorithm, the following equality holds
|d1 ∪ d2 | = |d| − 1; hence the algorithm terminates after at most 2|E(G)| calls.
For the second claim, the crucial observation is that we only need to store the
entries of g for a and m such that g(ām ) is nonempty. Since at most one entry is
defined in every call to the algorithm, and we can simply check if k ≡ a (mod m)
for all stored entries, the claim, and the theorem, follow.
3.2

MIN-AVG on the line

As an even more special underlying metric, we might consider the min-avg
problem on the line (on a path). For the min-max version this case is trivial, but

for the min-avg version its complexity is unclear: we do not know whether it is
in NP, although we expect it to be NP-hard.
On the positive side we can show that the problem is not strongly NP-hard.
Theorem 5. min-avg on the line can be solved in pseudopolynomial time.
The proof of Theorem 5 is deferred to the appendix, where we give a DP that
finds an optimal schedule in polynomial time for any instance with polynomially
bounded turnover times.

4

Approximation on general graphs

We will now present logarithmic approximations for both objectives. Note that
an O(log τmax )-approximation is readily achieved; simply treat the sets of clients
with equal turnover time as independent instances. For min-avg, the problem
with equal turnover times is simply tsp, for the min-max we get a problem
sometimes called the k-tsp, for which a 52 approximation is known [15]. Since
by rounding to powers of 2, we ensure there are O(log(τmax ) different turnover
times, we get Theorem 6 (a formal proof can be found in the appendix).
Theorem 6. min-max and min-avg rftt have an O(log τmax )-approximation.
In the case of min-max it is relatively simple to adapt this idea for an
O(log n)-approximation by appropriately reassigning clients to lower turnover
times, as per Theorem 7.
Theorem 7. min-max rftt has an O(log n)-approximation.
Proof. We start by assuming that every turnover time is a power of 2. Next, we
split up the instance into two new instances. To this end we first define a turnover
time k to be saturated if |{j ∈ V |τj = k}| ≥ k. In the first instance we retain the
set of vertices V1 with saturated turnover times, and in the second all vertices V2
with unsaturated turnover times. Now if all turnover times are saturated, then
τmax = O(n) and we can find a O(log n)-approximation using Theorem 6. So
what remains is to find a O(log n)-approximation for the second instance.
Since no turnover time is saturated, it is easy to see that we can partition
the vertices in V2 into dlog ne sets W1 , W2 , W4 , . . . , W2dlog ne , such that |Wi | ≤ i,
and such that τj ≥ i for all j ∈ Wi . For example we could first add all vertices
j with τj = i to Wi for i ≤ dlog ne, and then arbitrarily distribute vertices j
with τj > dlog ne among the sets that have space. We now produce a schedule
by visiting all clients in any set Wk on different days. This is feasible and
implies that at most log n clients are visited on a given day, which leads to
O(log n)-approximation factor, as required.
The approach of Theorem 6 does not trivially extend to the min-avg case.
However, we may combine our result on trees with the FRT tree embeddings [13],
to get a randomized O(log n)-approximation.

A more direct, and deterministic O(log n)-approximation is possible as well.
In particular, we use the simple heuristic of visiting each client on every day
that is a multiple of its turnover time, when turnover times are powers of 2. We
call such a schedule a synchronized solution, and show that gives a logarithmic
approximation.
The proof of this approximation factor, which is not trivial, works by show
that a synchronized schedule is no more costly than a non-decreasing schedule,
in which all tours are routed along a tree with turnover times non-decreasing
from the root. We then show how to transform any schedule to a non-decreasing
one, losing a logarithmic factor in the process. As a byproduct we show that the
analysis is tight, an that a non-decreasing schedule must be Ω(log n) times more
costly than OPT in the worst case. The proof of Theorem 8 can be found in the
appendix.
Theorem 8. min-avg rftt has an O(log n)-approximation.
It is an open question whether there exists a constant factor approximation
algorithm for the general case. We observe that the approach of first finding a tree
spanning all vertices and then using the algorithm of Section 3 is unsuccessful. In
fact there exist instances of the problem on a graph G with n vertices, such that
if we limit our attention to tours that for each day use only edges of a spanning
tree of G then the obtained solution is Ω(log n) approximated. This implies that
we need some new ideas, in order to improve the O(log n) approximation of the
previous theorem.

5

Conclusion

In this paper, we considered replenishment problems with fixed turnover times, a
natural inventory-routing problem that has not been studied before. We formally
defined the rftt problem and considered the objectives min-avg and min-max.
For the min-avg rftt, we showed that it is at least as hard as the intractable
Pinwheel Scheduling Problem on series-parallel graphs and we gave a 2approximation for trees. For the min-max objective we showed NP-hardness on
stars and gave a 6-approximation for tree metrics. We also presented a DP that
solved the min-avg rftt in pseudopolynomial time on line graphs. Finally, we
gave a O(log n)-approximation for the min-max objective on general metrics.
The results that we present should be considered as a first step in this area
and many problems remain open. An intriguing open problem is the complexity
of the of rftt on a tree. Namely, for min-avg variant we conjecture that the
problem is hard, and we ask whether the simple 2-approximation we provide
can be improved. For the min-max variant it is open whether the problem is
APX-hard and whether we can improve the 6-approximation,
Next to replenishing locations with routing aspects as we studied in this paper,
scheduling problems modeling maintenance or security control of systems, form a
class of problems to which this model naturally applies. It would be interesting to
study such fixed turnover time problems in combination with scheduling. Would
this combination allow for more definitive results?

References
1. Sanjoy Baruah and Joël Goossens. Scheduling real-time tasks: Algorithms and
complexity. In Handbook of Scheduling: Algorithms, Models, and Performance
Analysis. CRC Press, Boca Raton, 2003.
2. Sanjoy Baruah, Louis Rosier, Igor Tulchinsky, and Donald Varvel. The complexity
of periodic maintenance. In Proceedings of the International Computer Symposium,
pages 315–320, 1990.
3. Sanjoy K. Baruah, Rodney R. Howell, and Louis E. Rosier. Feasibility problems
for recurring tasks on one processor. Theor. Comput. Sci., 118(1):3–20, 1993.
4. Vincenzo Bonifaci and Alberto Marchetti-Spaccamela. Feasibility analysis of sporadic real-time multiprocessor task systems. Algorithmica, 63(4):763–780, 2012.
5. Chris Calabro, Russell Impagliazzo, Valentine Kabenets, and Ramamohan Paturi.
The complexity of unique k-sat: An isolation lemma for k-cnfs. Journal of Computer
and System Sciences, 74(3):386–393, 2008.
6. Mee Yee Chan and Francis Y. L. Chin. General schedulers for the pinwheel problem
based on double-integer reduction. IEEE Transactions on Computers, 41(6):755–768,
1992.
7. Mee Yee Chan and Francis Y. L. Chin. Schedulers for larger classes of pinwheel
instances. Algorithmica, 9(5):425–462, 1993.
8. Leandro C. Coelho, Jean-François Cordeau, and Gilbert Laporte. Thirty years of
inventory routing. Transportation Science, 48(1):1–19, 2013.
9. Sofie Coene, Frits C. R. Spieksma, and Gerhard J. Woeginger. Charlemagne’s
challenge: The periodic latency problem. Operations Research, 59(3):674–683, 2011.
10. Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, and Martin Wahlén.
Exponential time complexity of the permanent and the tutte polynomial. ACM
Transactions on Algorithms, 10(4):21:1–21:32, 2014.
11. Friedrich Eisenbrand, Nicolai Hähnle, Martin Niemeier, Martin Skutella, José
Verschae, and Andreas Wiese. Scheduling periodic tasks in a hard real-time
environment. In Proceedings of the 37th International Colloquium on Automata,
Languages, and Programming, pages 299–311. Springer, 2010.
12. Pontus Ekberg and Wang Yi. Schedulability analysis of a graph-based task model
for mixed-criticality systems. Real-Time Systems, 52(1):1–37, 2016.
13. Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences,
69(3):485–497, 2004.
14. Peter C. Fishburn and Jeffrey C. Lagarias. Pinwheel scheduling: Achievable densities.
Algorithmica, 34(1):14–38, 2002.
15. Greg N. Frederickson, Matthew S. Hecht, and Chul E. Kim. Approximation
algorithms for some routing problems. In Proceedings of the 17th International
Symposium on Foundations of Computer Science, pages 216–227, 1976.
16. Michael R. Garey and David S. Johnson. Computers and intractability: A guide to
the theory of NP-completeness. 1979.
17. Leszek Gasieniec, Ralf Klasing, Christos Levcopoulos, Andrzej Lingas, Jie Min, and
Tomasz Radzik. Bamboo garden trimming problem. In SOFSEM, pages 229–240.
Springer, 2017.
18. Robert Holte, Al Mok, Louis Rosier, Igor Tulchinsky, and Donald Varvel. The
pinwheel: A real-time scheduling problem. In Proceedings of the 22th Annual Hawaii
International Conference on System Sciences, volume 2, pages 693–702, 1989.

19. Tobias Jacobs and Salvatore Longo. A new perspective on the windows scheduling
problem. arXiv preprint arXiv:1410.7237, 2014.

20. Philip Klein and R Ravi. A nearly best-possible approximation algorithm for
node-weighted steiner trees. Journal of Algorithms, 19(1):104–115, 1995.

21. Al Mok, Louis Rosier, Igor Tulchinksy, and Donald Varvel. Algorithms and complexity of the periodic maintenance problem. Microprocessing and Microprogramming,
27(1-5):657–664, 1989.

A

Proof of Theorem 1

Proof. Given an instance p1 , ..., pn of Pinwheel Scheduling, create an instance
(G, τ ) of min-avg rftt. We define
V = {s, w1 , w, w2 } ∪ V 1 ∪ V 2 ,
where V i = {v1i , ..., vni } for i = 1, 2,
E = {(s, v)|v ∈ V 1 ∪ V 2 } ∪ {(wi , vji )|∀j; i = 1, 2} ∪ {(w1 , w), (w2 , w)},
and τw1 = τw2 = τw = 1, τvj1 = τvj2 = pj . All edge weights are 1. See Figure 1 for
an illustration.
We claim that the instance (G, τ ) has a solution of cost 6 if and only if
p1 , ..., pn is a feasible Pinwheel Scheduling instance.
For the ‘if’-direction, suppose we have a feasible pinwheel schedule. Then we
create a replenishment schedule as follows: we take the set of jobs visited on day k,
Jk = {vj1 , w1 , w, w2 , vj2 }, where job j is the job scheduled on day k in the pinwheel
solution (when no job is visited, pick one arbitrarily). The pinwheel schedule then
guarantees that the periods of jobs in V 1 ∪ V 2 are satisfied, while jobs w1 , w, w2
are visited every day, as required. Now since any tour (s, vj1 , w1 , w, w2 , vj2 , s) has
length 6, we can do this within the claimed cost.
For the ‘only if’-direction, note that any replenishment schedule must have
cost 6 at least, since no tour that visits w1 , w, w2 costs less than that. Moreover,
any tour visiting those three vertices that is not of the form (s, vj1 , w1 , w, w2 , vj2 , s),
will cost strictly more than 6. It follows that if the cost of the replenishment
schedule is 6, every tour visits at most one job from V 1 (and the same for V 2 ).
Since τvj1 = pj for all j, this directly implies that the Pinwheel Scheduling
instance is feasible.

Fig. 1. Instance created in the proof of Theorem 1.
v31
v21
v11

s
v12
v22
v32

B

w1
w
w2

Proof of Theorem 2

P
1
In 3-Partition, we are given 3m integers a1 , . . . , a3m and an integer B = m
i ai
such that B4 < ai < B2 for all i. The question is whether we can partition the
integers into m sets of three integers that add up to B [16].

Proof. Given an instance of 3-Partition, create a weighted star graph G with
the depot at the center and for every integer ai a leaf vertex attached with an
edge of weight ai /2. Finally set the turnover time to m for every leaf. We will
show that the rftt instance has value B if and only if we have a YES-instance
for 3-Partition.
Given a valid partition of the integers, clearly one can assign every set of 3
integers a unique day in 1, . . . , m and visit the associated leaf on every multiple
of that day for a valid rftt solution. That the opposite direction works as well
hinges on the fact that B4 < ai for all i, so we cannot visit more than 3 clients
on one day. Since after m days all clients must have been visited due to the
turnover times, it follows that the first m days of the schedule corresponds to a
valid partition.

C

Proof of Lemma 1

Proof. Let (G, τ̄ ) denote the instance found from (G, τ ) by rounding every
turnover time up to a power of 2. Since any schedule remains feasible if we round
up the turnover times, we have that OP T (G, τ̄ ) ≤ OP T (G, τ ) ≤ OP T (G, τ 0 ).
Suppose we have an optimal solution for (G, τ̄ ) in which T̄k is scheduled
on day k. We can construct a feasible schedule for (G, τ 0 ) by scheduling the
concatenation of T̄2k−1 and T̄2k on day k. The maximum tour length in this
schedule is at most twice that of the optimal solution for (G, τ̄ ) and every tour
from the original schedule is visited exactly twice in the new schedule, so this
yields a factor 2 increase in both the min-max and the min-avg objective.

D

A dynamic program that proves Theorem 5

In this section we will show how to solve the min-avg problem on the line in
pseudopolynomial time. Since we are minimizing the average, it is easy to see
that we can reduce this problem to two times the min-avg problem on the
half-line (a path with the depot in one of the leaves). On the half-line each vertex
i has a distance di ∈ N from the origin. Suppose vertices are numbered such
that d1 ≤ . . . ≤ dn . We present a pseudopolynomial time dynamic programming
agorithm for this problem, based on the following observations.
First of all, we note that on any tour visiting vertex j automatically visits
every vertex i < j. As in the tree case, we therefore assume that τi ≤ τj for i < j.
Thus, after visiting j, all i ≤ j have a remaining turnover time of τi . For the
dynamic program to work, we guess L, the day on which vertex n is visited for
the first time and try all guesses between 1 and τn .
The dynamic program now works as follows. Suppose we are given the optimal
solution for vertices 1, . . . , i − 1 when only considering the days 1, . . . , k. Now we
want to include i in the optimal solution for the first k days. If k < min{τi , L},
it is not necessary to visit i during the first k days, and hence it is optimal to
take the optimal solution for the first i − 1 vertices and k days. Otherwise, we
need to visit i on some day ` in {1, . . . , min{τi , L}}. Before day `, we only need

to visit the vertices 1, . . . , i − 1. Thus, we take the optimal ` − 1 tours for visiting
the first i − 1 vertices in the first ` − 1 days. After day `, all vertices have the
same remaining turnover time as they had at time zero. Hence, we can take the
optimal tours for the first i vertices and k − ` days.
Let φL (i, k) := the minimum cost of the first k tours visiting vertices 1, ..., i.
We initialize φL (0, k) = φL (i, 0) = 0 and we use the recursion:
(
φL (i − 1, k)
, if k < min{τi , L}
φL (i, k) =
min`=1,...,min{τi ,L} φL (i − 1, ` − 1) + di + φL (i, k − `) , else
The optimal solution is the schedule that corresponds to the value L ∈
{1, . . . , τn } minimizing φL (n, L)/L. Note that the algorithm runs in time O(nτn3 ),
implying the following.
Theorem 9. min-avg on the line can be solved in pseudopolynomial time.

E

Proof of Theorem 6

Proof. By Lemma 1 we may assume every τi is a power of 2 so that there are at
most log τmax different turnover times. We simply treat the sets of vertices with
the same turnover time as separate instances and concatenate the solutions. Our
result then follows from the fact that for all these instances a constant factor
approximation is available. In the case of the min-max objective we get the k-tsp
problem, where k is equal to the turnover time of the vertices in the instance. In
the case of min-avg, we need to minimize the sum over all k tours. But since all
turnover times are equal there is no advantage to visiting vertices on different
days, hence we recover a simple tsp problem.

F

Proof of Theorem 8 and tightness of analysis

This section provides two proofs of Theorem 8, which shows that we can get a
O(log n)-approximation for the min-avg objective as well. The first proof is a
direct application of metric tree embeddings.
Proof (Proof of Theorem 8). We will apply the FRT tree embedding [13] of
the initial instance and then use the 2-approximation for tree metrics to obtain
the final solution. Given the instance (G, τ ), let T be a random tree produced
by the tree metric approximation with O(log n) distortion. Then dG (u, v) ≤
dT (u, v) and E[dT (u, v)] ≤ O(log n)dG (u, v). Let S be the solution produced
by the 2-approximation for min-avg rftt on the tree metric T . Then E[S] ≤
2E[OP T (T, τ )] ≤ O(log n)E[OP T (G, τ )] by linearity of expectation on the sum
over the edges.
The second proof arises from a more natural algorithm given by a simple
greedy strategy. We round all periods to powers of 2 and delay visiting any

client for as long as possible. Next, for every day we use any constant factor
approximation for TSP to calculate a tour on the clients whose visit can no longer
be delayed. We call this a synchronized solution. It takes some work to show this
does indeed provide a logarithmic approximation though. We do this by showing
that any synchronized solution is no more costly than a non-decreasing solution,
in which every tour is based on a tree that has the clients ordered by ascending
turnover times from root to leaves. We then show that such a non-decreasing
solution costs at most O(log n) times the optimal solution , and provide an
example showing this analysis is tight. Moreover, we show that the optimal
non-decreasing solution is at most twice as costly as the optimal synchronized
solution. This implies that that any sub-logarithmic approximation algorithm
must avoid finding such solutions.
As always we will assume that turnover times are rounded to powers of 2. Let
us define a synchronized solution, as one where a client with turnover time 2i is
visited on each day that is a multiple of 2i , for all i. We define a non-decreasing
tree as a tree on the depot and subset of clients, such that the turnover times
on every path from the depot to the leafs are non-decreasing. A non-decreasing
solution is a solution in which for each day the tour is given by visiting the clients
of a non-decreasing tree in depth first order.
The following two lemmas show that optimal synchronized and non-decreasing
solutions differ in cost by at most a constant factor.
Lemma 6. The optimal synchronized solution costs at most two times the optimal non-decreasing solution.
Proof. Suppose we have a non-decreasing solution. Let Ti be the non-decreasing
tree associated with day i, for i ∈ N. We will show that we can find a set of trees
Ti0 for i ∈ N that cost at most as much as Ti on average, and such that any client
v appears in tree Ti if i is a multiple of τv . A synchronized solution can then be
found by taking the tour on day i to be a tour depth first search in Ti0 , losing a
factor 2.
Iteratively, from j = 0, . . . , log τmax , we build the new trees. In iteration j
and for all i, select all unmarked edges in Ti that are used on a path from the
depot to a client v with τv = 2j , and mark them. Then insert these edges in the
tree Tk0 for the earliest following day k that is a multiple of 2j , so k = d 2ij e2j .
We now show by induction that after iteration j, for each day k that is a
multiple of 2j , Tk is a tree connecting the depot to all clients v with turnover time
2j . The base case j = 0 follows from the fact that the trees Ti are non-decreasing
and must contain every client with turnover time 1. For higher j, it is easy to
see that Tk must contain a path from v to w for all clients v with τv = 2j and
some w with τw < 2j . But Tk already contains w by our inductive hypothesis
and the result follows.
We remark that we have corresponding converse result, as per Lemma 7.
Lemma 7. The optimal non-decreasing solutions costs at most two times the
optimal synchronized solution.

Proof. We may assume that any synchronized solution uses at most log(τmax ) + 1
distinct tours, lets label them T0 , . . . , Tlog(τmax ) , where Tj visits all clients with
turnover time at most 2j . Furthermore define ∆0 = c(T0 ) and ∆j = c(Tj ) −
c(Tj−1 ), for j = 1, . . . , log(τmax ). Then it holds that the cost of the synchronized
solution is
log(τmax )
X
1
csync =
∆j .
2j
j=0
Now note that we can create a non-decreasing tree for any day with 2j as its
largest power of 2 factor from the synchronized solution, by taking the union of
T0 , . . . , Tj where we shortcut every client v with τv < 2j in tour Tj . But the cost
of such a solution is
log(τmax )

X

cndecr =

j=0

=

logX
τmax
j=0

=

1
c(Tj )
2j

j
1 X
∆i
2j i=0

logX
τmax logX
τmax
i=0

≤2

logX
τmax
i=0

j=i

1
∆i
2j

1
∆i = 2csync
2i

Our main result follows from showing that we can always find a non-decreasing
solution of cost O(log n) times OP T . We use the following tree pairing Lemma
by Klein and Ravi [20].
Lemma 8. Given any tree T and an even subset S of its vertices, there is a
pairing of vertices covering S such that the tree-path induced by the pairs are
edge-disjoint.
Using the tree pairing Lemma 8, we will construct non-decreasing trees
to approximate arbitrary trees. First we define the notations needed for the
algorithm.
A non-decreasing arc a({u, v}) of {u, v} is the arc between u and v that points
from the client with lower turnover time to the one with higher turnover time
(ties are broken arbitrarily). The client with the lower (higher) turnover time is
denoted by L({u, v}) (H({u, v})). We denote by U the unpaired clients and A
the arcs of the non-decreasing tree being constructed, and require that all arcs
must eventually point away from the depot.
Lemma 9. Given an arbitrary tree T of cost c(T ), there is a non-decreasing tree
of cost at most dlog nec(T ).

Algorithm 2 Algorithm to create non-decreasing tree from arbitrary tree
1: Initialize U ← V and A ← ∅.
2: while |U | > 0 do:
3:
Find an edge-disjoint pairing P of a largest even subset of U .
4:
for {u, v} ∈ P do:
5:
A ← A ∪ a({u, v}).
6:
U ← U \ H({u, v}).
7:
end for
8: end while

Proof. Let T be a tree. We will construct a non-decreasing tree T 0 by iteratively
pairing off the vertices and directing each pair in a non-decreasing manner.
In the algorithm, we apply the pairing procedure dlog ne times to get a nondecreasing tree of the desired cost. In each round, we pair a largest subset of V
such that the pairs induce edge disjoint paths in T . Then we direct each pair
{u, v} in ascending order of turnover times and delete the client with higher
turnover time from consideration. These arcs are added to the arc set of T 0 .
We can think of each pair as a connected component represented by the client
with the smallest turnover time. In the end, T 0 is finalized when no unpaired
vertices remain. Note that picking the vertex of minimum turnover time as the
representative per connected component ensures that the final tree is indeed
directed away from the depot.
In each round, we used each edge of T at most once since all pair-induced
paths were edge-disjoint. Let κ(t) be the number of vertices at the beginning
of round t. Since each round paired off either all vertices or all but one vertex,
we have κ(t) = dκ(t − 1)/2e. So the total number of rounds is dlog ne. Hence
c(T 0 ) ≤ dlog nec(T ).
Proof (Proof of Theorem 8). Given an optimal solution, let Ti be the minimum
Steiner tree on the set of clients visited on day i, which costs no more than
the tour of that day. Using Lemma 9 we can find non-decreasing trees Ti0 of
cost at most O(log n)c(Ti ). Turning the trees into tours loses only a constant
factor, which gives us a non-decreasing solution of cost O(log n) times OP T . By
Lemma 6 we may then turn this solution into a synchronized one as required,
concluding the proof.
The bound in the proof of Theorem 8 is tight; as there exists a class of
instances where requiring a solution to be non-decreasing introduces a logarithmic
optimality gap. Together with Lemma 7, this implies that our algorithm does no
better than O(log n) as well.
Proposition 1. There exists a class of instances in which there is a logarithmic
optimality gap between the optimal and the optimal non-decreasing solution.
To show that the bound in the proof of Theorem 8 is tight, we first show that
Lemma 9 is tight. Consider the following sequence of sequences (a0 , a1 , . . .) where

a0 = (1) and ai+1 is generated by alternatingly taking an element from ai and
then from the sequence bi = (2i + 1, 2i + 2, . . . , 2i+1 ). For example:
–
–
–
–
–

a0 = 1
a1 = 1, 2
a2 = 1, 3, 2, 4
a3 = 1, 5, 3, 6, 2, 7, 4, 8
···

Then define the (unweighted) graph Gi as the path graph with 2i vertices,
i
where the jth vertex has turnover time 2aj −1 . See Figure 2 for an example.

Fig. 2. Illustration of G2 , (turnover times in circles)

1

4

2

8

The minimum spanning tree in Gi costs 2i − 1. It is easy to check that
the decreasing spanning tree produced by Algorithm 2 costs i2i−1 . Moreover,
since the solution produced attaches every vertex to a nearest vertex with lower
turnover time, it must be optimal.
To show tightness of our main theorem, we will define another class of graphs
Hi for i ≥ 1 that are constructed from {Gi }. The idea is to make τj copies of
each terminal j, and then connect them in a regular way, for example like in
Figure 3.

Fig. 3. Illustration of H2
τi = 1

τi = 4

τi = 2

τi = 8

Formally Hi is constructed as follows. For simplicity of description, we assume
that Gi is planarly embedded from left to right, and we assume that we keep a
planar embedding of Hi during construction.
We first copy node 1 to Hi . Now we work from left to right, starting from
the second node. When we are at node j, we put τj copies of j vertically above
each other and to the right of the copies of j − 1 in Hi . Then we connect them

to the copies of j − 1 in Hi such that the graph remains planar and all copies of
j − 1 have the same degree, and all copies of j have the same degree. This can
be done in only one way. Furthermore we identify vertex 1 with the depot.
Proposition 2. The instance induced by Hi has a logarithmic optimality gap
between the optimal and the optimal non-decreasing solution.
Proof. There exists an obvious solution that visits exactly one client of each
turnover time per day, that costs 2(2i − 1).
Now suppose we impose non-decreasing constraints. In this case we need to
use (on average) at least one edge pointing from a client with a lower turnover
time to one with a higher turnover time per day. But from our reasoning on the
decreasing minimum spanning tree in Gi , we find that the cheapest set of edges
that contains at least one edge pointing from a client with turnover time 2i to
one with lower turnover time for all i, costs at least i2i−1 . Therefore the optimal
solution under non-decreasing constraints is at least a logarithmic factor more
expensive than the optimal solution.

