Serving Online Requests with Mobile Servers

arXiv:1404.5510v2 [cs.DS] 11 Oct 2016

Abdolhamid Ghodselahi and Fabian Kuhn
Department of Computer Science, University of Freiburg
79110 Freiburg, Germany
{hghods,kuhn}@cs.uni-freiburg.de
Abstract
We study an online problem in which a set of mobile servers have to be moved in order to efficiently
serve a set of requests that arrive in an online fashion. More formally, there is a set of n nodes and a set of k
mobile servers that are placed at some of the nodes. Each node can potentially host several servers and the
servers can be moved between the nodes. There are requests 1, 2, . . . that are adversarially issued at nodes
one at a time. An issued request at time t needs to be served at all times t′ ≥ t. The cost for serving the
requests is a function of the number of servers and requests at the different nodes. The requirements on how
to serve the requests are governed by two parameters α ≥ 1 and β ≥ 0. An algorithm needs to guarantee at
all times that the total service cost remains within a multiplicative factor of α and an additive term β of the
current optimal service cost.
We consider online algorithms for two different minimization objectives. We first consider the natural
problem of minimizing the total number of server movements. We show that in this case for every k, the
competitive ratio of every deterministic online algorithm needs to be at least Ω(n). Given this negative
result, we then extend the minimization objective to also include the current service cost. We give almost
tight bounds on the competitive ratio of the online problem where one needs to minimize the sum of the total
number of movements and the current service cost. In particular, we show that at the cost of an additional
additive term which is roughly linear in k, it is possible to achieve a multiplicative competitive ratio of 1 + ε
for every constant ε > 0.

1

Introduction

Consider of a company with several project teams which are located at different places. Moving a whole team
to a new location is expensive, however depending on where new customers arrive, it might still be desirable to
do. The cost for serving the customers at a certain location clearly depends (in a possibly non-linear way) on
the number of project teams and on the number of customers at the location. Alternatively think of a distributed
service that is offered on a large network such as the Internet. To offer the service, a provider might have a
budget to place k servers in the network. The best placement of servers depends on the distribution of the
users of the distributed service. As the set of users might grow (or even change arbitrarily) over time, from
time to time, we might have to move some of the servers, even though migrating a whole server might be a
relatively costly thing to do. These scenarios could be generally seen as a problem where servers are relatively
large entities such that while they can be moved, doing this is a relatively costly operation, irrespective of, e.g.,
between which nodes a movement occurs. The above scenarios are applications of the abstract problem studied
in this paper. The problem studied in this paper can be formally modeled as follows.
Assume two parameters α and β are given such that α ≥ 1 and max {α − 1, β} ≥ 1. There is a set V of n
nodes and there are k mobile servers, where each server has to be placed at one of the nodes. Further, there are
requests that arrive at the nodes in an online fashion and which need to be “permanently” served, i.e. an issued
request at time t has to be served at all times t, t + 1, . . .. We assume that any node can potentially host an
arbitrary number of servers. Formally, the cost for serving the requests at each node v, which is called service
cost of node v, is given by a general cost function that depends on v, on the number of requests at node v, as
well as on the number of servers placed at v. Generally, the more requests there are at some node, the more it
1

costs to serve these requests. Further, if we place more servers at a given node, the cost for serving the requests
at this node becomes smaller (formally defined in Section 2.2).1 The requests arrive one by one and the task of
an algorithm is to plan the movements of the k servers in a way to keep a feasible configuration of the k servers
at all times. A configuration of servers is called feasible whenever the total service cost, that is the summation
of service costs for all nodes, is upper bounded by αSt∗ + β, where, St∗ is the optimal total service cost at time
t.
We consider two different objective functions. We first study a natural variant of the problem where the
goal is to minimize the total number of movements. For this setting, we show that any deterministic online
algorithm has a competitive ratio of at least Ω(n), independent of the value of k.
Given this negative result, we then consider an objective function where the cost at time t is the sum of
the total number of movements up to time t and the total service cost at time t (shown by Cost A
t for a given
algorithm A). We study a simple online greedy algorithm which a) only moves when it needs to move because
the configuration is not feasible any more and b) always moves a server which improves the service cost as
much as possible. We show that the total number of movements up to a time t of this online greedy algorithm
can be upper bounded as a function of the optimal service cost St∗ at time t. Most significantly, we show that
even for α = 1, for any ε > 0, as long as β = Ω(k + k/ε), at all times t, the cost Cost A
t of the greedy algorithm
O
A
can be upper bounded by the cost Cost t of an optimal algorithm as Cost t ≤ (1 + ε)Cost O
t + O(β + k log k).
We also show that this result is essentially tight. In particular, an additive term which is at least linear in k is
unavoidable (even for much larger multiplicative competitive ratio).

1.1 Related Work
In its basic version, where we only consider the movement cost, the problem considered in the present paper
generally falls into a class of movement problems introduced in [7]. In this version, the most similar of the
classic problems is the k-server problem [17] or more specifically the paging problem [20] (equivalent to the
k-server problem with uniform distances). In the k-server problem, every new request has to be served by
moving some server to the location of the request and the only cost considered is the total movement cost. The
k-server problem is well studied. For general metric spaces, the best competitive ratios known are 2k − 1 [15]
and Õ(log2 k log3 n) [4]. The authors of [4] use a problem called the allocation problem (AP) to solve the
k-server problem. The AP and also the results on the AP have some resemblances to the model and results in
the present paper when considering the objective function based on service and movement costs. However, like
k-server, in the AP the requests are served only once they arrive at the requested points while in our model the
requests are permanently served and servers are not necessarily moved to the requested points.
When considering the variant of our problem where the service cost is included in the objective function,
the problem can be seen as an online version of the mobile facility location problem (MFLP) with uniform
distances. MFLP in general metrics was introduced in [7, 11] as a movement problem. It can be seen as a
generalization of the standard k-median and facility location problems [11]. The k-median and facility location
problems have been widely studied in both operations research and computer science [3, 5, 6, 8, 12, 14]. In
[1, 11], MFLP is modeled in such a way that the algorithm moves each facility and client to a point where in
the final configuration, each client is at a node with some facility. The goal is to minimize the total movement
cost of facilities and clients. The movement cost between the clients and the final configuration points could be
interpreted as a service cost somewhat similar to what we use in this paper. Note that since in our case, requests
need to be permanently served, we cannot model the service cost as a movement cost.
Classically, the cost of serving a request in the facility location problem is given by the distance from the
request to the facility to which it is assigned. In a uniform metric, this corresponds to the most basic cost
function that can be studied in our framework (service cost is equal to the number of requests at nodes with
no servers). As described, we significantly generalize this basic service cost model. In the context of facility
1

The most basic cost function would incur a service cost of x whenever x requests are at a node with no server and a service cost of
0 for all requests at nodes with at least one server.

2

location, a similar approach was used in [13]. More concretely, in [13], it is assumed that the cost of a facility
increases as a function of the requests it needs to serve.
There exist various natural models in which the locations of requests are not known in advance, and a
solution must be built or maintained gradually over time without any knowledge about future requests like
online facility location problem. The first algorithm for online facility location was introduced in [18]. For a
broad discussion of models and results on online facility location problem, we refer to the survey in [10].
Finally, the problem studied in this paper has some resemblance to learning problems [2, 16, 19]. Somewhat similarly to expert learning algorithms where in essence, one converges to the “right set of experts”, our
algorithm has to converge to the “right set of nodes” to place its servers. However, in our case, the cost will
usually be dominated by the total movement cost, i.e., the total cost for replacing the servers. In learning,
switching to a different set of experts is usually not considered a (main) cost.

2

Problem Statement

We are given a set V of n nodes and there is a set of k servers. Further, there are requests 1, 2, . . . that
adversarially arrive one at a time. Moreover two parameters α and β are given such that
α ≥ 1 and

max {α − 1, β} ≥ 1.

(1)

We assume that at time t ≥ 1, request t arrives at node v(t) ∈ V . For a node v ∈ V , let rv,t be the number
of requests at node v after t requests have arrived, i.e., rv,t := |{i ≤ t : v(i) = v}|. In order to keep the total
service cost small, an algorithm can move the servers between the nodes (if necessary, for answering one new
request, we allow an algorithm to also move more than one server). However throughout the execution, each
of the k servers is always placed at one
Pof the nodes v ∈ V . We define a configuration of servers by integers
fv ∈ N0 for each v ∈ V such that v∈V fv = k. We describe such a configuration by a set of pairs as
F := {(v, fv ) : v ∈ V }. The initial configuration is denoted by F0 .
Service Cost: We implicitly assume that if a node v has some servers, all requests at v are served by these
servers. This also implies that the “assignment” of requests to servers can change over time and the service
cost is not cumulative. Depending on the number of servers and the number of requests at a node v ∈ V ,
an algorithm has to pay some service cost to serve the requests located at v. This service cost of node v is
defined by a service cost function σv such that σv (x, y) ≥ 0 is the cost for serving y requests if there are x
servers at node v. For convenience, for t ≥ 1, we also define σv,t (x) := σv (x, rv,t ) to be the service cost
with x servers
P t. For some configuration F , we denote the total service cost at time t by
P at node v at time
St (F ) := v∈V σv,t (fv ) = v∈V σv (fv , rv,t ).
Feasible Configuration: We define a configuration F to be feasible at time t iff
St (F ) < α · St∗ + β

(2)

where St∗ is the optimal total service cost at time t, i.e. St∗ := min St (F ). Note that St∗ is not necessarily the
F

same as the total service cost StO of an optimal algorithm O at time t. We say that a configuration F ∗ is an
optimal configuration at time t if St (F ∗ ) = St∗ .

Feasible Solution: For a given algorithm A, we denote the solution at time t by FtA := F A (i) : i ∈ [0, t] ,
where F A (t) is the configuration after reacting to the arrival of request t and where F A (0) = F0 . Note that for
two integers a ≤ b, [a, b] := {a, . . . , b} denotes the set of all integers between a and b. Further, for an integer
a ≥ 1, we use [a] as a short form to denote [a] := [1, a]. The service cost of an algorithm A at time t is denoted
by StA := St (F A (t)).
Movement Cost: We define the movement cost MtA of given algorithm A to be the total number of server
movements by time t. Generally, for two feasible configurations, F = {(v, fv ) : v ∈ V } and F ′ = {(v, fv′ ) : v ∈ V },
we define the distance χ(F, F ′ ) between the two configurations as follows:
X

1 X
fv − fv′ .
(3)
χ(F, F ′ ) :=
max 0, fv − fv′ = ·
2
v∈V

v∈V

3

The distance χ(F, F ′ ) is equal to the number of movements that are needed to get from configuration F to
configuration F ′ (or vice versa). Based on the definitionP
of χ, we can express the movement
cost of an algorithm

A with solution FtA = F A (i) : i ∈ [0, t] as MtA = ti=1 χ F A (i − 1), F A (i) .

2.1 Objective Functions

As described in Section 1, we consider two different objective functions.
Minimizing the Movement Cost: The goal is to keep the number of movements as small as possible. In other
A
A
words, the cost Cost A
t of an algorithm A is defined as Cost t := Mt .

Minimizing the Combined Cost: The goal here is to minimize the overall cost of an algorithm A, that is, we
A
A
aim to keep Cost A
t := St + Mt as small as possible.

2.2 Service Cost Function Properties
The service cost function σ has to satisfy a number of natural properties. First of all, for every v ∈ V , σv (x, y)
has to be monotonically decreasing in the number of servers x that are placed at node v and monotonically
increasing in the number of requests y at v.
∀v ∈ V ∀x, y ∈ N0 : σv (x, y) ≥ σv (x + 1, y)

∀v ∈ V ∀x, y ∈ N0 : σv (x, y) ≤ σv (x, y + 1)

(4)
(5)

Further, the effect of adding additional servers to a node v should become smaller with the number of servers
(convex property in x) and it should not decrease if the number of requests gets larger. Therefore, for all v ∈ V
and all x, y ∈ N0 , we have
σv (x, y) − σv (x + 1, y) ≥ σv (x + 1, y) − σv (x + 2, y)

σv (x, y) − σv (x + 1, y) ≤ σv (x, y + 1) − σv (x + 1, y + 1)

(6)
(7)

In the following, whenever clear from the context, we omit the superscript A in the algorithm-dependent
quantities defined above.

3

Contributions

The following theorem provides a lower bound for any deterministic online algorithm that solves the problem
of minimizing the total number of movements as described in Section 2.1. We remark that this lower bound
as well as the lower bound in Theorem 3.3 even hold for the simple (and natural) scenario, where the service
cost at a node with at least 1 server is 0 and the service cost at a node with 0 servers is equal to the number of
requests at that node.
Theorem 3.1 (Lower Bound). Assume that we are given parameters α and β which satisfy (1) and assume
that the objective is to minimize the number of movements. Then, for any online algorithm A, there exists an
execution and a time t > 0 such that the competitive ratio between the number of movements by A and the
number of movements of an optimal offline algorithm is at least n/2. More precisely for all MtO > 0 there is
an execution such that MtA ≥ n2 · MtO .
Given the large lower bound of Theorem 3.1, we adapt the objective function to also include the service
cost. The following Theorems 3.2 and 3.3 upper and lower bound the achievable competitive ratio in this case.
In Section 5.1, we describe a simple, deterministic online algorithm A with the following properties. For two
given parameters α and β, A guarantees that at all times t ≥ 0, (2) is met. Algorithm A guarantees (2) while
keeping the total movement cost small. More precisely, we prove the following main theorem.
Theorem 3.2 (Upper Bound). There is a deterministic algorithm A such that for all times t ≥ 0, the following
statements hold.
4

• If α = 1 and β = Ω k +

• If α = 1 and β = Ω



k
ε



k·log k
log log k

for an abitrary ε > 0,
O
Cost A
t ≤ (1 + ε)Cost t + O(β + k log k).


, for every ε ≥ log log k/ log1−δ k and any constant 0 < δ ≤ 1,
O
Cost A
t ≤ (1 + ε)Cost t + O (β) .

We also prove an almost matching lower bound. The total cost of both online and optimal offline algorithms
are bounded by functions of the optimal service cost.
Theorem 3.3 (Lower Bound). Given α ≥ 1 and β satisfying (1), consider any deterministic online algorithm
A and assume that O is an optimal offline algorithm. Then, when considering the combined objective function,
there exist an execution and a time t > 0 such that the total costs of A and O can be bounded as follows.
• For α = 1 and β = Ω(k/ε) for any ε > 0, it holds that



1+ε
A
Cost t ≥ 1 + ε 1 −
Cost O
t + Ω(β + k log k).
k
• For α = 1 and β = Ω
obtain



k·log k
log log k

Cost A
t

≥





for every ε ≥ log log k/ log1−δ k and any constant 0 < δ ≤ 1 we


1+ε
1+ε 1−
k



Cost O
t

+Ω



k · log k
log log k



.

Choosing α > 1: The results of the above theorems all hold for α = 1, i.e., an algorithm is always forced
to move to a configuration which is optimal up to the additive term β. Even if α is chosen to be larger than 1,
as long as we want to guarantee a reasonably small multiplicative competitive ratio (of order o(k)), an additive
term of order Ω(k) is unavoidable. In fact, in order to reduce the additive term to O(k), α has to be chosen to be
of order kδ for some constant δ > 0. Note that in this case, the multiplicative competitive ratio grows to at least
α ≫ 1. However, it might still be desirable to choose α > 1. In that case, it can be shown that the movement
cost MtA of our simple greedy algorithm A only grows logarithmically with the optimal service cost St∗ (where
the basis of the logarithm is α). As an application, this for example allows to be (1 + ε)-competitive for any
constant ε > 0 against an objective function of the form γ · StA + MtA even if γ is chosen of order k−O(1) .

4

Minimizing the Number of Movements

We provide a proof for our lower bound as claimed in Theorem 3.1 in Section 3. As we can assume that each
node either has 0 or 1 servers, we slightly overload notation and simply denote a feasible configuration by a set
F ⊂ V of size |F | = k.

4.1 Lower Bound

We first fix A to be any deterministic online algorithm and O to be any optimal offline algorithm. For proving
the statement of Theorem 3.1, we distinguish two cases, depending on the number of servers k. In both cases,
we define iterations to be subsequences of requests such that A needs to move at least once per iteration. The
number of movements by A is therefore at least the number of iterations of a given execution.
Case k ≤ ⌊n/2⌋: At the beginning, we place a large number of requests on any k − 1 nodes that initially
have servers. We choose this number of requests sufficiently large such that no algorithm can ever move any of
these k − 1 servers. This essentially reduces the problem to k = 1 and n − k + 1 nodes.
To bound the number of movements by O, we then consider intervals of n − k iterations such that A is
forced to move in each iteration. During each interval, the requests are distributed in such a way that at the
5

beginning of the i-th iteration of the interval there are at least n − k − i + 1 nodes such that if any offline
algorithm places a server on one of these nodes, Condition (2) remains satisfied throughout the whole interval.
Hence, there exists an offline algorithm that moves at most once in each interval and therefore the number of
movements by O is upper bounded by the number of intervals.
Case k > ⌊n/2⌋: In this case, there is some resemblance between the constructed execution and the lower
bound constructions for the paging problem. For simplicity assume that there are n = k + 1 nodes (we let
requests arrive at only k + 1 nodes). At the beginning of each iteration we locate a sufficiently large number of
requests on the node without any server of A such that (2) is violated. Thus, A has to move at least one server
to keep (2) satisfied. By contrast, O does not need to move in each iteration. There is always a node which
will not get new requests for the next k interations and therefore O only needs to move at most once every k
iterations to keep (2) satisfied.
Proof of Theorem 3.1. Consider any request sequence. First we provide a partitioning of the request sequence
as follows. The request sequence is partitioned into iterations. Iteration 0 is the empty sequence and for every
i ≥ 1, iteration i consists of a request sequence of a length dependent on α, β, and the iteration number i. The
request sequence of an iteration i is chosen dependent on a given online algorithm A such that A must move at
least once in iteration i. We will see that while A needs to move at least once per iteration, there is an offline
algorithm which only moves once every at least n/2 iterations.
In the proof, we reduce all the cases to two extreme cases. In the first case, we reduce the original metric
on a set of n nodes with k ≤ ⌊n/2⌋ servers to the case where there is only 1 server. To do this, we first place
sufficiently many requests on k − 1 nodes that have servers at the beginning of execution (for simplicty, assume
that we place an unbounded number of requests on these nodes). This prevents any algorithm from moving its
servers from these k − 1 nodes during the execution and hence we can ignore these k − 1 nodes an servers in
our analysis. In contrast, for the second case where k > ⌊n/2⌋, we assume that w.l.o.g., k = n − 1 by simply
only placing requests on the k nodes which have servers at the beginning and on one additional node.
In the following, we let ti denote the end of an iteration i. Moreover suppose I is the total number of
iterations, where we assume that I ≡ 0 (mod max {k, n − k}).
Case k ≤ ⌊n/2⌋: The idea behind the execution is to uniformly increase the number of requests on the n − k
nodes that do not have the server at the beginning of an iteration i (i.e., at time ti−1 ) in such a way that A has to
move at least once to satisfy (2) at the end of iteration i. Moreover the distribution of requests guarantees that
any node without the server at time ti−1 is a candidate to have the (free) server of A at time ti . Let vtA denote
the node on which A locates its server at time t and let U (t) be the set of all nodes without server at time t.
Moreover, let vt∗ be a node which has the largest number of requests among all nodes at time t. The node with
the largest number of requests at the end if an iteration i, i.e. vt∗i , is chosen such that vt∗i 6= vtAi−1 . At time 0, we
have ru = 0 for all nodes u. The distribution of requests at the end of iteration i is as follows:

∀u ∈ U (ti−1 ) \ vt∗i : ru = rvt∗ + max {β, 1} ,
(8)
i−1

rvtA

i−1

rvt∗

i

= rvt∗

i−1

,

(9)

= (α − 1) · St∗i + rvt∗

i−1

+ β.

(10)

Note that since it is clear from the context, we skip the second subscript (i.e., t) when referring to the number
of requests at a node (cf. Section 2).
Claim 4.1. The above execution guarantees that A has to move at least once per iteration. Further, there
exists an offline algorithm A that moves its servers at most I/(n − k) times.
Proof. Consider any interval of n − k iterations such that the first iteration of this interval has ending
time τ1 and the finishing time of the last iteration (or the finishing time of the interval) is τn−k . Further,
suppose the previous interval has finished at t̂. Obviously, if this is the first interval, t̂ = 0. Let U :=
6

Sτn−k  A
U (t̂) \ t=τ
vt denote the set of nodes which have not had the server of A during this interval. The
1
offline algorithm for all iterations of this interval, locates its server either on node vτAn−k if set U is empty
or on some node in U , otherwise. The case in which U is empty indicates that every node in U (t̂) has had
the server of A exactly once
n withinothe interval. Whenever the offline algorithm needs to move, it locates
its server at a node in U ∪ vτAn−k . On the one hand and according to (8), node vτAn−k or any node in U
(in the case this set is not empty) has at least rvt∗ + max {β, 1} requests at the end of each iteration i
i−1
that is in this interval. Therefore, the offline service cost at ti is


StAi ≤ (α − 1) · St∗i + 2rvt∗ + β + (n − k − 2) · max {β, 1} + rvt∗
(11)
i−1

i−1

On the other hand, the optimal service cost is


St∗i = (n − k − 1) · max {β, 1} + rvt∗

i−1

using (8), (9), and (10). Hence (11) and (12) imply that



+ rvt∗

(12)

i−1

StAi < αSt∗i + β.

(13)

This guarantees that offline algorithm does not need to move more than once during any interval of n − k
iterations. In other
o at the beginning of the interval, the offline algorithm decides to locate its server
n words,
A
to a node in U ∪ vτn−k if it needs because it knows the behaviour of the online algorithm in advance as
well as the request sequence. According to (13), this one movement by A is sufficient to keep (2) satisfied
within the interval. Therefore, the offline algorithm moves at most I/(n − k) times.
At the end of each iteration i, if the online algorithm has not moved yet within the iteration i then we
have vtAi−1 = vtAi . Thus,
StAi = (α − 1) · St∗i + rvt∗

i−1


+ β + (n − k − 1) · max {β, 1} + rvt∗

i−1



(14)

with respect to (8), (9), and (10). Therefore due to (12) and (14) we have StAi = αSt∗i + β. This implies
that the online algorithm must had moved at least once to guarantee
∀i : vtAi−1 6= vtAi .
Thus A has to move once per iteration and then the claim holds.
Corollary 4.2. The Claim 4.1 implies that
MtO ≤

MtA
.
n−k

where t be the ending time of (c · (n − k))-th iteration for any integer c ≥ 1.
Proof. It follows the fact that MtO ≤ MtA .
Case k > ⌊n/2⌋: Here when we have more servers than half of the nodes, we assume, w.l.o.g. n = k + 1.
This is doable by letting the requests arrive at a fix set of nodes of size k + 1 including k servers. Therefore, at
each time there is only one node without a server in which this situation holds for any algorithm. Let v̄tA denote
the node without any server of A at time t. We force A to move in each iteration i by putting large enough
number of requests on v̄tAi−1 while any optimal offline algorithm only moves one of its servers after at least k
iterations. Consider an interval of k iterations starting from the first iteration of this interval with ending time
7

τ1 and ending at the last iteration at time τk . For any iteration i of this interval the distribution of the requests
at the end of the iteration is as follows.
rv̄tA

i−1

= αSt∗i + max {β, 1} .

(15)

According to (15) the optimal service cost does not change during the interval, i.e. Sτ∗i = Sτ∗i +1 for all i ∈ [k−1]
of the current interval.
Claim 4.3. The above execution guarantees that A has to move at least once per iteration while the
number of movements by any optimal offline algorithm is at most I/k.
Proof. At the end of iteration i, assume v̄tAi−1 = v̄tAi , then we have
StAi = αSt∗i + max {β, 1} ≥ αSt∗i + β

(16)

using (15). It implies that the online algorithm must had moved at least once to guarantee
∀i : v̄tAi−1 6= v̄tAi .
The optimal offline algorithm, by contrast, need to move a server from v̄τAk to v̄τA1 during the interval
with respect to the request distribution in (15). The node v̄τAk is the node has αSt̂∗ + max {β, 1} requests
within the interval due to (15) where t̂ is the ending time of any iteration of the previous interval. Hence,
at the end of any iteration i in the interval, the optimal offline service cost equals the optimal service cost
and thus (2) remains satisfied. Consequently it implies that at most one movement by optimal offline
algorithm is sufficient during the interval. This concludes that the number of movements by any optimal
offline algorithm is at most I/k in this case.
Let t be the ending time of (c · max {k, n − k})-th iteration for any integer c ≥ 1. Using Corollary 4.2 and
Claim 4.3
n
MtA ≥ max {n − k, k} · MtO ≥ · MtO .
2
Thus the claim of the theorem holds.

5

Minimizing Movements and Service Cost

We will now extend the objective function used in Section 4 by also including the service cost. We will see
that this allows us to be able to compete against an optimal offline algorithm O. In the rest of this section, first
we devise a simple and natural online greedy algorithm. We then analyze the algorithm and provide an almost
tight lower bound.

5.1 Algorithm Description
The goal of our algorithm is two-fold. On the one hand, we have to guarantee that the service cost of the
algorithm is always within some fixed bounds of the optimal service cost. On the other hand, we want to achieve
this while keeping the overall movement cost low. Specifically, as we are given α and β in which (1) holds, we
guarantee that at all times (2) remains satisfied. Condition (2) is maintained in the most straightforward greedy
manner. Whenever after a new request arrives, (2) is not satisfied, the algorithm greedily moves servers until
(2) holds again. Hence, as long as (2) does not hold, the algorithm moves a server that reduces the total service
cost as much as possible. The algorithm stops moving any server as soon as the validity of (2) is restored.
Whenever the algorithm moves a server, it does a best possible move, i.e., a move that achieves the best
possible service cost improvement. Thus, the algorithm always moves a server from a node where removing a

8

server is as cheap as possible to a node where adding a server reduces the cost as much as possible. Therefore,
for each movement m, we have
src
vm

∈ arg min {σv,τm (fv,m−1 − 1) − σv,τm (fv,m−1 )} and

(17)

dst
vm

∈ arg max {σv,τm (fv,m−1 ) − σv,τm (fv,m−1 + 1)} ,

(18)

v∈V

v∈V

where arg minv and arg maxv denote the sets of nodes minimizing and maximizing the respective terms.

5.2 Analysis Overview
While the algorithm itself is quite simple, its analysis turns out relatively technical. We thus first describe the
key steps of the analysis by discussing a simple case. We assume that the service cost at any node is equal
to 0 if there is at least one server at the node and the service cost is equal to the number of requests at the
node, otherwise. Further, we assume that we run the algorithm of 5.1 with parameters α = 1 and β = 0, i.e.
after each request arrives, the algorithm moves to a configuration with optimal service cost. Note that these
parameter settings violate Condition (1) and we will therefore get a weaker bound than the one promised by
Theorem 3.2.
First, note that in the described simple scenario, the algorithm clearly never puts more than one server to
the same node. Further, whenever the algorithm moves a server from a node u to a node v, the overall service
cost has to strictly decrease and thus, the number of requests at node v is larger than the number of requests at
node u. Consider some point in time t and let
rmin (t) :=

min

v∈V :fv,t =1

rv,t

be the minimum number of requests among the nodes v with a server at time t. Hence, whenever at a time t, the
algorithm moves a server from a node u to a node v, node u has at least rmin (t) requests and consequently, node
v has at least rmin(t) + 1 requests. Further, if at some later time t′ > t, the server at node v is moved to some
other node w, because the algorithm always removes a server from a node with as few requests as possible, we
have rmin (t′ ) ≥ rmin (t) + 1. Consequently, if in some time interval [t1 , t2 ], there is some server that is moved
more than once, we know that rmin (t1 ) < rmin (t2 ). In our analysis, we partition time into phases, where the
first phase starts at time 0 and where phases are maximal time intervals in which each server is moved at most
once (cf. Def. 5.1 in the formal analysis of the algorithm).
The above argument implies that after each phase rmin increases by at least one and therefore at any time
t in phase p, we have rmin (t) ≥ p − 1 and at the end of phase p, we have rmin (t) ≥ p. In Section 5.3, the
more general form of this statement appears in Lemma 5.1. There, γp is defined to be the smallest service cost
improvement of any movement in phase p (γp = 1 in the simple case considered here), and Lemma 5.1 shows
that rmin grows by at least γp in phase p. Assume that at some time t in phase p, a server is moved from a node
u to a node v. Because node u already had its server at the end of phase p − 1, we have ru,t = rmin (t) ≥ p − 1.
Consequently, at the end of phase p, there is at least one node (the source of the last movement) that has no
server and at least p − 1 requests. The corresponding (more technical) statement in our general analysis appears
in Lemma 5.3.
We will bound the total cost of the online algorithm and an optimal offline algorithm from above and below,
respectively, as a function of the optimal service cost. Hence, the ratio between these two total costs provides
the desired competitive factor. Our algorithm guarantees that at all times, the service cost is within fixed bounds
of the optimal service cost (in the simple case here, the service cost is always equal to the optimal service cost).
Knowing that there are nodes with many requests and no servers, therefore allows to lower bound the optimal
service cost. In the general case, this is done by Lemmas 5.6 and 5.7. In the simple case, considered here, as at
the end of phase p, there are k nodes with at least p requests (the nodes that have servers) and there is at least
one additional node with at least p − 1 requests, we know that at the end of phase p, the optimal service cost is
at least p − 1. Consequently, the online algorithm (in the simple case) pays exactly the optimal service cost (as
9

mentioned before, in the general case, the service cost is within fixed bounds of the optimal service cost) and at
most (p − 1)k as movement cost. Hence, the total cost paid by online algorithm is at most a factor k + 1 times
the optimal service cost since the optimal service cost is at least p − 1. By choosing α which is slighly larger
than 1 and a larger β (β ≥ k), the algorithm becomes more lazy and one can show that the difference between
the number of movements of A and the optimal service cost becomes significantly smaller. Also note that by
construction, the service cost of A is always at most αSt∗ + β ≤ αStO + β.
When analyzing our algorithm, we mostly ignore to take into account the movement cost of an optimal
offline algorithm. We only exploit the fact that by the time A decides to move a server for the first time, any
other algorithm must also move at least one server and therefore the optimal offline cost becomes at least 1.

5.3 Upper Bound Analysis
In the following, we show that how to upper bound the combined cost (service cost and movement cost) of our
online algorithm A by a function of the combined cost of an optimal offline algorithm O. Clearly, the algorithm
at all times t ≥ 0 guarantees that the service cost can be bounded as
StA < αSt∗ + β ≤ αStO + β.

(19)

In order to upper bound the combined cost, it therefore suffices to study how the movement cost MtA of the
online algorithm grows as a function of the combined optimal offline algorithm cost. Let O be an optimal
offline algorithm and let F O (t) be the configuration of O at time t. Recall that χ(F0 , F O (t)) denotes the total
number of movements required to move from the initial configuration to configuration F O (t). We therefore
O
O
O
∗
O
A
have Cost O
t = St + Mt ≥ St + χ(F0 , F (t)). In order to upper bound Mt as a function of Cost t , we will
∗
O
upper bound it as a function of St + χ(F0 , F (t)).
Instead of directly dealing with χ(F0 , F O (t)), we will make use of the fact that our analysis works for a
general cost function σ satisfying the conditions given in (4), (5), (6), and (7). Given a service cost function σ,
consider a function σ ′ which is defined as follows:
∀v ∈ V, ∀x ∈ {0, . . . , k} , ∀y ∈ N0 : σv′ (x, y) := σv (x, y) + max {0, fv (0) − x}
where fv (t) is the number of servers at time t on node v. Clearly, σ ′ also satisfies the conditions given in (4),
(5), (6), and (7). In addition, for any time t and any configuration F = {(v, fv ) : v ∈ V }, we have
X
St′ (F ) =
σv′ (fv , rv,t )
v∈V

=

X

v∈V
(3)

(σv (fv , rv,t ) + max {0, fv (0) − fv })

= St (F ) + χ(F0 , F )

(20)

where St′ (F ) refers to the total service cost w.r.t. the new cost function σ ′ . Hence, St′ (F ) exactly measures the
sum of service cost and movement cost of a configuration F . Of course now, in all our results, St∗ corresponds
to the combination of service and movement cost of an optimal configuration F ∗ .
We are now going to analyze the algorithm of Section 5.1. In the following, whenever we refer to the
algorithm introduced in Section 5.1, we omit the superscript A. In our analysis, we will bound the total costs
of optimal offline algorithm O and online algorithm A from below and above, respectively, as functions of
optimal service cost and thus provide the upper bound (competitive factor) promised in Theorem 3.2. Hence
we first go through calculating the optimal service cost.
For the analysis of the described online algorithm, we partition the movements into phases p = 1, 2, . . . ,
where roughly speaking, a phase is a maximal consecutive sequence of movements in which no server is moved
src,A
dst ,A
twice. We use mp to denote the first movement of phase p (for p ∈ N). In addition, we define vm
and vm
src to
to be the nodes involved in the m-th server move, where we assume that A moves a server from node vm
dst
vm . Formally, the phases are defined as follows.
10

Definition 5.1 (Phases). The movements are divided into phases p = 1, 2, . . . , where phase p starts with
movement mp and ends with movement mp+1 − 1. We have m1 = 1, i.e., the first phase starts with the first
movement. Further for every p > 1, we define
n
o
src
dst
mp := min m > mp−1 : ∃ m′ ∈ [mp−1 , m − 1] s.t. vm
= vm
.
(21)
′
For a phase p ≥ 1, let λp := mp+1 − mp be the number of movements of Phase p.

5.3.1

Optimal Service Cost Analysis

The algorithm moves servers in order to improve the service cost. Throughout the rest of the paper, we use
A to denote the time of the mth movement. For a given movement m, we use γ(m) > 0 to denote service
τm
cost improvement of m. Further, we use F0 to denote the initial
 configuration of the k servers and for a given
A = (v, f A ) : v ∈ V
(deterministic) algorithm A, for any m ≥ 1, we let Fm
be the configuration of the k
v,m
A servers).
servers for A after m server movements (i.e., after m server movements of A, node v has fv,m
γ(m) :=
=

Sτm (Fm−1 ) − Sτm (Fm )


σvm
dst ,τ (fv dst ,m−1 ) − σv dst ,τ (fv dst ,m )
m
m
m
m
m


src ,τ (fv src ,m ) − σv src ,τ (fv src ,m−1 ) .
− σvm
m
m
m
m
m

(22)

For each Phase p, we define the improvement γp of p and the cumulative improvement Γp by Phase p as
follows
p
X
γi , Γ0 := 0, γ0 := 0.
(23)
γp :=
min
γ(m) and Γp :=
m∈[mp ,mp+1 −1]

i=1

We are now ready to prove our first technical lemma, which lower bounds the cost of removing servers
from nodes with servers (for all v ∈ V such that fv ≥ 1) at any point in the execution. The result of following
Lemma implies that removing any server of an optimal configuration during some phase p increases the optimal
service cost at least Γp−1 (and Γp at end of phase p) since the servers of an optimal configuration are located at
places with maximum number of requests.
Lemma 5.1. Let m be a movement and, F = {(v, fv ) : v ∈ V } be the configuration of the algorithm at any
point in the execution after movement m and let t ≥ τm be the time at which the configuration F occurs. Then,
for all times t′ ≥ t and for all nodes v ∈ V , if fv > 0 it holds that
σv,t′ (fv − 1) − σv,t′ (fv ) ≥ Γp−1 ,
where p is the phase in which movement m occurs.
Proof. We will show that for each server movement m ∈ N of the algorithm, it holds that
∀v ∈ V : fv,m > 0 =⇒ σv,τm (fv,m − 1) − σv,τm (fv,m ) ≥ Γp−1 ,

(24)

where p is the phase in which movement m occurs (i.e., the claim of the lemma holds immediately after movement m). The lemma then follows because (i) any configuration {(v, fv ) : v ∈ V } occurring after movement
m is the configuration Fm′ for some movement m′ ≥ m, (ii) the values Γp−1 are monotonically increasing
with p, and (iii) by (7), for all v ∈ V , the value σv,t (f − 1) − σv,t (f ) is monotonically non-decreasing with t.
It therefore remains to prove (24) for every m, where p is the phase of movement m. We prove a slightly
stronger statement. Generally, for a movement m′ and a phase p′ , let Vpdst
′ ,m′ be the set of nodes that have
received a new server by some movement m′′ ≤ m′ of Phase p′ . Hence,
n
o
dst
v ∈ V : ∃ movement m′′ ≤ m′ of Phase p′ s.t. vm
.
Vpdst
′ ,m′ :=
′′ = v
11

We show that in addition to (24), it also holds that
dst
∀v ∈ Vp,m
: fv,m > 0 =⇒ σv,τm (fv,m − 1) − σv,τm (fv,m ) ≥ Γp .

(25)

We prove (24) and (25) together by using induction on m.
Induction Base (m = 1): The first movement occurs in Phase 1. By (23), Γ0 = 0 and by (4), we also have
σv,t (f − 1) − σv,t (f ) ≥ 0 for all times t ≥ 0, all nodes v ∈ V , and all f ≥ 1. Inequality
 (24) therefore clearly
dst = v dst and showing (25)
holds for m = 1. It remains to show that also (25) holds for m = 1. We have V1,1
1
for m = 1 therefore reduces to showing that σvdst ,τ1 (fvdst ,1 − 1) − σvdst ,τ1 (fvdst ,1 ) ≥ Γ1 = γ1 , which follows
1
1
1
1
directly from (22) and (23).
Induction Step (m > 1): We first show that Inequalities (24) and (25) hold immediately before movement m
and thus,

∀v ∈

∀v ∈ V

dst
Vp,m−1

: fv,m−1 > 0 ⇒ σv,τm (fv,m−1 − 1) − σv,τm (fv,m−1 ) ≥ Γp−1 ,
: fv,m−1 > 0 ⇒ σv,τm (fv,m−1 − 1) − σv,τm (fv,m−1 ) ≥ Γp .

(26)
(27)

If m is not the first movement of Phase p, Inequalities (26) and (27) follow directly from the induction hypothesis (for m − 1) and from (7). Let us therefore assume that m is the first movement of Phase p. Note
dst
= ∅ and (27) therefore trivially holds. Because m > 1, we know that in this
that in this case Vp,m−1
case p ≥ 2. From the induction hypothesis and from (7), we can therefore conclude that for every node
dst
(every node v that is the destination of some server movement in Phase p − 1), we have
v ∈ Vp−1,m−1
σv,τm (fv,m−1 − 1) − σv,τm (fv,m−1 ) ≥ Γp−1 . Note that for all these nodes, we have fv,m−1 > 0. Because m
src ∈ V dst
is the first movement of Phase p, Definition 5.1 implies that vm
p−1,m−1 . Applying (17), we get that for
src ,τ (fv src ,m−1 − 1) − σv src ,τ (fv src ,m−1 ) ≥ Γp−1 and
all v ∈ V , σv,τm (fv,m−1 − 1) − σv,τm (fv,m−1 ) ≥ σvm
m
m
m
m
m
therefore (26) also holds if m ≥ 2 is the first movement of some phase.
src , v dst , we have f
all nodes v ∈
/ vm
We can now prove (24) and (25). For
v,m = fv,m−1 and we further
m
 src
dst
dst
dst
dst
have Vp,m = Vp,m−1 ∪ vm . For v ∈
/ vm , vm , (24) and (25) therefore directly follow from (26) and (27),
src ∈
dst
. It therefore suffices to
respectively. For the two nodes involved in movement m, first note that vm
/ Vp,m−1
show that
src ,m = 0
fvm
or

as well as

src ,τ (fv src ,m − 1) − σv src ,τ (fv src ,m )
σvm
≥ Γp−1 ,
m
m
m
m
m

≥ Γp .
σvm
dst ,τ (fv dst ,m − 1) − σv dst ,τ (fv dst ,m )
m
m
m
m
m

(28)
(29)

src ,m = fv src ,m−1 − 1 and f dst
We have fvm
dst ,m−1 + 1. Inequality (28) therefore directly follows from
vm ,m = fvm
m
(26) and from (6). For (29), we have

σvm
dst ,τ (fv dst ,m − 1) − σv dst ,τ (fv dst ,m )
m
m
m
m
m
(22)

=

(26)

≥

src ,τ (fv src ,m ) − σv src ,τ (fv src ,m − 1) + γ(m)
σvm
m
m
m
m
m

(23)

Γp−1 + γ(m) ≥

Γp .

This completes the proof of (24) and (25) and thus the proof of the lemma.
For each phase number p, let θp := τmp be the time of the the first movement mp of Phase p. Before
continuing, we give lower and upper bounds on γp , the improvement of Phase p. For all p ≥ 1, we define
ηp := (α − 1) · Sθ∗p + β.

(30)

Lemma 5.2. Let m be a movement of Phase p and let F ∗ = arg min St (F ) be the optimal configuration at
time τm . We then have

F

ηp
χ(Fm−1 , F ∗ )

≤ γ(m) ≤ ηp+1 .
12

Proof. For the upper bound, observe that we have
γ(m) ≤ Sτm (Fm−1 ) − Sτ∗m
as clearly the service cost cannot be improved by a larger amount. Because at all times t, the algorithm keeps
the service cost below αSt∗ + β, we have Sτm −1 (Fm−1 ) < αSτ∗m −1 + β ≤ αSτ∗m + β. The upper bound on
γ(m) follows from (30) and because Sτ∗m ≤ Sθ∗p+1 .
For the lower bound on γ(m), we need to prove that χ(Fm−1 , F ∗ ) ≥ ηp /γ(m). Because the algorithm
moves a server at time τm , we know that Sτm (Fm−1 ) ≥ αSτm (F ∗ ) + β and applying the Definition (30)
of ηp , we thus have Sτm (Fm−1 ) − Sτm (F ∗ ) ≥ ηp . Intuitively, we have χ(Fm−1 , F ∗ ) ≥ ηp /γ(m) because
the algorithm always chooses the best possible movement and thus every possible movement improves the
overall service cost by at most γ(m). Thus, the number of movements needs to get from Fm−1 to an optimal
configuration F ∗ has to be at least ηp /γ(m). For a formal argument, assume that we are given a sequence of
ℓ := χ(Fm−1 , F ∗ ) movements that transform configuration Fm−1 into configuration F ∗ . For i ∈ [ℓ], assume
that the ith of these movements moves a server from node ui to node vi . Further, for any i ∈ [ℓ] let fi be the
number of servers at node ui and let fi′ be the number of servers at node vi before the ith of these movements.
Because the sequence of movements is minimal to get from Fm−1 to F ∗ , we certainly have fi ≤ fui ,m−1 and
fi′ ≥ fvi ,m−1 . For the service cost improvement γ of the ith of these movements, we therefore obtain


γ = σvi ,τm (fi′ ) − σvi ,τm (fi′ + 1) − σui ,τm (fi − 1) − σui ,τm (fi )
(6)

≤ σvi ,τm (fvi ,m−1 ) − σvi ,τm (fvi ,m−1 + 1)

− σui ,τm (fui ,m−1 − 1) − σui ,τm (fui ,m−1 )
≤ γ(m).

The last inequality follows from (17),(18), and (22). As the sum of the ℓ service cost improvements has to be
at least ηp , we obtain ℓ = χ(Fm−1 , F ∗ ) ≥ ηp /γ(m) as claimed.
We can now lower bound the distribution of requests at the time of each movement.
Lemma 5.3. Let m be a movement of Phase p (for p ≥ 1). Then, there are integers ψv ≥ 0 for all nodes v ∈ V
such that
X
ηp
ψv ≥ k +
and
γ(m)
v∈V

∀t ≥ τm ∀v ∈ V : ψv > 0 =⇒ σv,t (ψv − 1) − σv,t (ψv ) ≥ Γp−1 .

Proof. It suffices to prove the statement for t = τm . For larger t, the claim then follows from (7). Consider an
optimal configuration
F ∗ = {(v, fv∗ ) : v ∈ V }
at the time τm of movement m. Let us further consider the configuration Fm−1 of the algorithm immediately
before movement m. Consider a pair of nodes u and v such that fu∗ > fu,m−1 and fv,m−1 > fv∗ . By the
optimality of F ∗ , we have
σu,τm (fu∗ − 1) − σu,τm (fu∗ ) ≥ σv,τm (fv,m−1 − 1) − σv,τm (fv,m−1 ).

(31)

Otherwise, moving a server from u to v would (strictly) improve the configuration F ∗ . By Lemma 5.1, we have
σv,τm (fv,m−1 − 1) − σv,τm (fv,m−1 ) ≥ Γp−1 for all nodes v for which fv,m−1 > 0. Together with (31), for all
v ∈ V for which max {fv,m−1 , fv∗ } > 1, we obtain
σv,τm (max {fv,m−1 , fv∗ } − 1) − σv,τm (max {fv,m−1 , fv∗ }) ≥ Γp−1 .
13

(32)

P
To prove the lemma, it therefore suffices to show that v∈V max {fv,m−1 , fv∗ } ≥ k + ηp /γ(m), as we can
then set ψv := max {fv,m−1 , fv∗ } and (32) implies the claim of the lemma. By (3), we have
X
X
max {fv,m−1 , fv∗ } = k +
max {0, fv∗ − fv,m−1 } = k + χ(Fm−1 , F ∗ ).
v∈V

v∈V

We therefore need that χ(Fm−1 , F ∗ ) ≥ ηp /γ(m), which follows from Lemma 5.2.
In the next lemma, we derive a lower bound on Sθ∗p , the service cost of optimal configuration when Phase p
starts. For each phase p ≥ 1, we first define S p as follows.


γp−2
γp−2
For p ≥ 3 : S p := 1 + (α − 1)
(33)
β, and S 1 := S 2 := 1.
· S p−1 +
γp−1
γp−1
Lemma 5.4. For all p ≥ 1, we have Sθ∗p ≥ S p .
Proof. We prove the lemma by induction on p.
Induction Base (p = 1, 2): Using (20) we have Sθ∗1 ≥ 1 and since S 1 = S 2 = 1, we get Sθ∗2 ≥ Sθ∗1 ≥ S 2 =
S1.
Induction Step (p > 2): We use the induction hypothesis to assume that the claim of the lemma is true up to
Phase p and we prove that it also holds for Phase p + 1. Therefore by the induction hypothesis, for all i ∈ [p],
Sθ∗p ≥ S p .

(34)

 ηi+1
η
, · · · , γpp . As a consequence of (30) and
For all i ∈ [p], we define η i := (α − 1)S i + β and δi := max γi+1
implies that
(34), we get that ηi ≥ η i for all i ∈ [p]. In the following, let p′ ∈ [2, p] be some phase. Lemma 5.3P
after the last movement m of Phase p′ , there are non-negative integers ψv (for v ∈ V ) such that v∈V ψv ≥
′
k+ηp′ /γp′ ≥ η p′ /γp′ and for all times t ≥ τm , for all v ∈ V for which ψv > 0, σv,t (ψ
Pv −1)−σv,t (ψv ) ≥ Γp −1 .
As
there
are
only
k
servers
for
any
feasible
configuration
F
=
{(v,
f
)},
we
have
f
=
k
and
therefore
v
v∈V v
P
v∈V (ψv − fv ) ≥ η p′ /γp′ . For any v ∈ V for which ψv > fv , by using (6), we get σv,t (fv ) ≥ (ψv − fv )Γp′ −1 .
Hence, after the last movement of Phase p′ , for any feasible configuration F , we have St (F ) ≥ St∗ ≥
At the beginning of Phase p + 1 (for p ≥ 2), the total optimal service cost therefore is
p−2

p−1

i=1

i=1

X
X
η p′
γi · δi .
(δi − δi+1 ) · Γi =
Γp′ −1 ≥ δp−1 Γp−1 +
′
p ∈[2,p] γp′

Sθ∗p+1 ≥ max

η p′
′
γp′ Γp −1 .

(35)

We define ζi for all i ∈ [3, p] as follows:
ζi :=

i−2
X
j=1

γj · δj .

(36)

Using the definition of δi , we thus have
ζp+1 = ζp + γp−1 δp−1 = ζp + η p

γp−1
.
γp

Considering the definition of η i we get
ζp+1



γp−1
= ζp · 1 + (α − 1)
γp



+β·

γp−1
.
γp

We therefore have ζp+1 = S p+1 directly from (33) and thus the claim of the lemma follows.
14

In order to explicitly lower bound the optimal service cost after p phases, we need the following technical
statement.
Lemma 5.5. Let ℓ ≥ 2 be an integer and consider a sequence c1 , c2 , . . . , cℓ > 0 of ℓ positive real numbers and
let cmax = max ci and cmin = min ci . Further, let λ ≥ 0 be an arbitrary non-negative real number. We have
i∈[ℓ]

i∈[ℓ]

(I)

ℓ
X
ci−1
i=2

(II)

ℓ 
Y
i=2

ci

≥ (ℓ − 1) ·

ci−1
1+λ
ci





≥

cmin
cmax



1+λ

1
ℓ−1

,



cmin
cmax



1
ℓ−1

!ℓ−1

.

Proof. The first part of the claim follows from the means inequality (the fact that the arithmetic mean is larger
than or equal to the geometric mean). In the following, we nevertheless directly prove both parts together. We
let x = (x1 , . . . , xℓ ) ∈ Rℓ be a vector ℓ real variables and we define multivariate functions f (x) : Rℓ → R and
g(x) : Rℓ → R as follows:
f (x) :=

ℓ
X
xi−1
i=2

xi

and

g(x) :=

ℓ 
Y
i=2

xi−1
1+λ
xi



.


We further define X ⊂ Rℓ as X := (z1 , . . . , zℓ ) ∈ Rℓ | ∀i ∈ [ℓ] : cmin ≤ zi ≤ cmax . We need to show
that for x ∈ X, f (x) and g(x) are lower bounded by the right-hand sides of Inequalities (I) and (II) above,
respectively. Note that X is a closed subset of Rℓ and because cmin > 0, both functions f (x) and g(x) are
continuous when defined on X. The minimum for x ∈ X is therefore well-defined for both f (x) and g(x).
We show that both f (x) and g(x) attain their minimum for
∗

x :=

(x∗1 , . . . , x∗ℓ ),

where ∀i ∈ [ℓ] :

x∗i

= cmin ·



cmax
cmin

 i−1

ℓ−1

.

Note that x∗ is the unique configuration x ∈ X to the following system of equations
x1 = cmin ,

xℓ = cmax ,

∀i ∈ {2, . . . , ℓ − 1} : xi ∈

xi−1
xi
=
.
xi
xi+1

(37)

Because we know that min f (x) = f (x∗ ) and min g(x) = g(x∗ ), it is therefore sufficient to show that for
x∈X

x∈X

any y ∈ X that does not satisfy (37), f (y) and g(y) are not minimal. Let us therefore consider a vector
y = (y1 , . . . , yℓ ) ∈ X that does not satisfy (37). First note that both f (x) and g(x) are strictly monotonically
increasing in x1 and strictly monotonically decreasing in xℓ . If either y1 > cmin or yℓ < cmax , it is therefore
clear that f (y) and g(y) are both not minimal (over X). Let us therefore assume that y1 = cmin and yℓ = cmax .
y
y0
From the assumption that y does not satisfy (37), we then have an i0 ∈ {2, . . . , ℓ − 1} for which iy0i−1 6= yi i+1
0
0
√
and thus yi0 6= yi0 −1 yi0 +1 . We define a new vector y ′ = (y1′ , . . . , yℓ′ ) ∈ X as follows. We have yi′0 =
√
yi0 −1 yi0 +1 and yi′ = yi for all i 6= i0 and we will show that f (y ′ ) < f (y) and g(y ′ ) < g(y). Define
C :=

Y

i∈[2,ℓ]\{i0 ,i0 +1}

15



yi−1
1+λ
yi



.

We then have
!

′
y
y
y
y
i
i
−1
i
−1
0
0
0
+ i0
+
−
f (y) − f (y ′ ) =
y i0
yi0 +1
yi′0
yi0 +1
"
! 
#
 

′ 
y
y
y
y
i −1
i
i −1
g(y) − g(y ′ ) =
1+λ 0
· 1 + λ i0
·C
· 1+λ 0
− 1 + λ 0′
y i0
yi0 +1
y i0
yi0 +1
"
!#

yi′0
yi0 −1
y i0
yi0 −1
=
+
+
−
· λC.
y i0
yi0 +1
yi′0
yi0 +1


Note that λ ≥ 0 and C > 0. In both cases, we therefore need to show that


√
y i0
yi0 −1
∀yi0 ∈ [cmin , cmax ] \
+
>
yi0 −1 yi0 +1 :
y i0
yi0 +1

yi′0
yi0 −1
+
yi′0
yi0 +1

y

This follows because the function h : [cmin , cmax ] → R, h(z) := i0z−1 +
√
[cmin , cmax ] and it has a stationary point at z = yi0 −1 yi0 +1 ∈ [cmin , cmax ].

z
yi0 +1

!

.

(38)

is strictly convex for z ∈

As long as (α − 1)Sθ∗p < β, the effect of the (α − 1)Sθ∗p -term on ηp (and thus of the αSt∗ term in (2)) is
relatively small. Let us therefore first analyze how the service cost grows by just considering terms that depends
on β (and not on α).
Lemma 5.6. For all p ≥ 3, we have
Sθ∗p

≥ min



1
β
, β · (p − 2) · (2k)− p−2
α−1



.

Proof. Assume that Sθ∗p < β/(α − 1) as otherwise the claim of the lemma is trivially true. By Lemma 5.4,
γp−2
using α ≥ 1, for all p ≥ 3, we get S p ≥ S p−1 + γp−1
β. Plugging in S 2 ≥ 0, induction on p therefore gives
Sθ∗p ≥ S p ≥ β ·

p−1
X
γi−1
i=2

γi

(39)

for all p ≥ 3. We define γmin = min {γ1 , . . . , γp−1 } and γmax = max {γ1 , . . . , γp−1 }. By Lemma 5.2 and
because η1 ≤ · · · ≤ ηp−1 , we have γmin ≥ η1 /k and γmax ≤ ηp . From α ≥ 1 and (30), we have η1 ≥
(α − 1) + β since we know Sθ∗p ≥ 1 for p ≥ 1 regarding to (20). Further, we have ηp = (α − 1)Sθ∗p + β < 2β.
We therefore have γmin ≥ [(α − 1) + β]/k and γmax < 2β and thus
γmin
(α − 1) + β (1) max {β, 1}
1
≥
.
≥
≥
γmax
2kβ
2kβ
2k
The lemma now follows from (39) and from Inequality (I) of Lemma 5.5.
n
o
β
On the other hand, as soon as Sθ∗p > max 1, α−1
, the effect of the β-term in (2) becomes relatively small.
As a second case, therefore, we analyze how the service cost grows by just considering terms that depends on
α (and not on β).

β
Lemma 5.7. Let p0 ≥ 2 be a phase for which S p0 ≥ S p0 −1 ≥ S0 := max 1, α−1
. For any phase p > p0 ,
we have
!p−p0
√
p−p0
α−1
S0
∗
·α 2 .
≥
S θp ≥ S 0 · 1 +
1
2k
(2k) p−p0
16



γ
Proof. By Lemma 5.4, using β ≥ 0, for all p > p0 , we get S p ≥ 1 + (α − 1) γp−2
· S p−1 . Induction on p
p−1
therefore gives

p−1
Y
γi−1
∗
(40)
S θp ≥ S p ≥ S p 0 ·
1 + (α − 1)
γi
i=p0

for all p ≥ p0 . Similarly to before, we define γmin = min {γp0 −1 , . . . , γp−1 } and γmax = max {γp0 −1 , . . . , γp−1 }.
By Lemma 5.2, the assumptions regarding p0 , and because the values ηi are non-decreasing in i, we have
max {(α − 1) + β, 2β}
ηp0 −1
≥
and
k
k
γmax ≤ ηp ≤ (α − 1)Sθ∗p + β ≤ 2(α − 1)Sθ∗p .

β
The last inequality follows because Sθ∗p ≥ S p ≥ S p0 ≥ max 1, α−1
and by applying (1). We can now apply
Inequality (II) from 5.5 to obtain

 1 !p−p0
γmin p−p0
∗
Sθp ≥ S p ≥ S p0 · 1 + (α − 1)
γmax

! 1 p−p0
max {(α − 1) + β, 2β} p−p0 
≥ S p0 · 1 + (α − 1)
.
(41)
2k(α − 1)Sθ∗p
γmin ≥

In the following, assume that

Sθ∗p


≤ max 1,

β
α−1



α

p−p0
2

.

(42)

Note that if (42) does not hold, the claim of the lemma is trivially true. By replacing Sθ∗p on the right-hand side
of (41) with the upper bound of (42), we obtain

 1 p−p0

Sθ∗p

≥ S p ≥ S p0


· 1 + (α − 1) · 

≥ S p0 ·

1+

≥ S p0 ·

1+

(α − 1) + β
n
o p−p0 
β
2k(α − 1) max 1, α−1 α 2
!p−p0

α−1
1 √
(2k) p−p0 α
!p−p0
√
α−1
(2k)

1
p−p0

≥

p−p0




p−p0
S p0
·α 2 .
2k


β
.
The lemma then follows because we assumed that S p0 ≥ max 1, α−1
5.3.2

Optimal Offline Algorithm Total Cost

Service Cost: In order to minimize the service cost, we can simply bound the service cost of O as follows
SθOp ≥ Sθ∗p .
Movement Cost: To simplify our analysis, we take no notice of movement cost by optimal offline algorithm
since it has no substantial effect on the competitive factor we will provide since O has to pay at least the optimal
service cost which we show it is large enough. The total cost of optimal offline algorithm, therefore, is bounded
as follows
∗
O
O
(43)
Cost O
θp = Mθp + Sθp ≥ Sθp .
17

5.3.3

Online Algorithm Total Cost

Service Cost: The online algorithm like any other algorithm has to keep the service cost smaller than a linear
function of optimal service cost as mentioned in (2). In other words, the configuration of servers at any time
has to be feasible as defined in Section 2. Thus
SθAp < αSθ∗p + β.

(44)

Movement Cost: First, using Definition 5.1 we bound the number of movement in each phase.
Observation 5.8. For each Phase p ≥ 1, we have λp ≤ k.
Proof. As an immediate consequence of Definition 5.1, we obtain that the maximum number of movements in
each phase is at most k. Let m > mp and consider the movements [mp , m]. We prove that if m < mp+1 , no
two the movements in [mp , m] move the same server. The claim then follows because there are only k servers.
For the sake of contradiction, assume that there is some server i that is moved more than once and let m′ and
m′′ (m′ , m′′ ∈ [mp , m], m′ < m′′ ) be the first two movements in [mp , m], where server i is moved. We clearly
dst = v src and Def. 5.1 thus leads to a contradiction to the assumption that m < m
have vm
′
p+1 .
m′′
As a result of above observation and Lemma 5.6 and Lemma 5.7, it is possible to prove the following lemma
to bound the number of online algorithm movements by means of optimal service cost.
Lemma 5.9. For any α ≥ 1 and β satisfying (1), there is a deterministic online algorithm A, such that for all
times t ≥ 0, the total movement cost MtA is bounded as follows.
• If α = 1, for any ℓ ≥ 1, ε > 0, and β ≥ k(2k)1/ℓ /ε, we have
MtA ≤ ε · St∗ + O(ℓk).
• For α ≥ 1 + ε where ε > 0 is some constant and any β satisfying (1), we have




k
log k
A
∗
, logα k + logα
.
Mt ≤ k · O 1 + logα St + min
log log k
1+β
Proof. First note that by Observation 5.8, the movement cost of our algorithm by time θp is at most
Mθp ≤ (p − 1)k + 1 ≤ pk.

(45)

Together with the lower bounds on Sθ∗p of Lemmas 5.6 and 5.7, this allows to derive an upper bound on the
movement cost of our algorithm as a function of Sθ∗p . Note that as all upper bound claimed in the lemma have
an additive term of O(k) (with no specific constant), it is sufficient to prove that the lemma holds for all time
t = θp , where p ≥ 2 is a phase number.
Let us first consider the case where α = 1. Because in that case β/(α − 1) is unbounded, we can only
apply Lemma 5.6 to upper bound the movement cost as a function of St∗ . We choose ℓ ≥ 1 and assume that
β ≥ k(2k)1/ℓ /ε for ε > 0. Together with (45), for p ≥ ℓ + 2, Lemma 5.6 then gives
1

Sθ∗p ≥

1
1
k
k(2k) ℓ
· (p − 2) · (2k)− ℓ = (p − 2) ≥ (Mθp − 2k).
ε
ε
ε

(46)

The first part of lemma 5.9 then follows because the total movement cost for the first ℓ + 2 phases is at most
O(ℓk). The special cases are obtained as follows. For β = Ω (k + k/ε), we set ℓ = Θ(log k) andevery ε > 0,
whereas for β = Ω(k log k/ log log k), we set ε = Θ(log log k/ log 1−δ k) and ℓ = Θ 1δ · logloglogk k for constant
0 < δ ≤ 1.
18

Let us therefore move to the case where α > 1. Let p0 be the first phase p0 ≥ 2 for which Sθ∗p ≥ S0 ,
0

β
where S0 = max 1, α−1
as in Lemma 5.7. Further, we set p1 = p0 + ⌈2 logα (2k)⌉. Using Lemma 5.7, for
p ≥ p1 , we have
p−p1
p1 −p0
p−p1
S0
· α 2 α 2 ≥ S0 · α 2 .
S θp ≥
2k
We therefore get
!


Sθ∗p
2k
∗
≤ k p0 + 1 + 2 logα Sθp + logα
.
Mθp ≤ k · p ≤ k p1 + 2 logα
S0
S0
The second claim of lemma 5.9 then follows by showing that
p0 = O min

 log k

, logα k .
log log k

If S0 = 1, we have p0 = 2. Otherwise, we can apply Lemma
 5.6 to upper bound p0 as the smallest value p0
β
= β(p − 2)(2k)−1/(p−2) . For α = O logloglogk k , the assumption that α is at least 1 + ε for some
for which α−1

constant ε > 0 gives that p0 = Θ logloglogk k . Otherwise, (i.e., for large α), we obtain p0 = Θ(logα−1 k) =
Θ(logα k).
Note that by choosing α > 1, thendependency of o
the movement cost MtA on the optimal service cost St∗ is
k
are dominated by log k.
only logarithmic because terms min logloglogk k , logα k and logα 1+β

Proof of Theorem 3.2. Putting (43), (44), and Lemma 5.9 all together conclude the claim of theorem.

5.4 Lower Bound
The aim of this section is to prove our lower bound theorem stated in Section 3. As discussed in Section 3, the
lower bound even holds for a natural special case where each node v ∈ V can only have either 0 or 1 servers.
Assume that we are given parameters α ≥ 1 and β such that (1) holds and an algorithm A which guarantees
that (2) remains satisfied at all times t. In the following, let O be any optimal offline algorithm. Given A, we
construct an execution in which A has to perform a large number of movements while the optimal service cost
does not grow too much. Analogously to the analysis of the upper bound, we divide time into phases such that
in each phase, A has to move Ω(k) servers and the optimal service cost grows as slowly as possible. For p
phases, we define a sequence of integers k/3 ≥ n1 ≥ n2 ≥ . . . np ≥ 1 and values Γ1 < Γ2 < · · · < Γp . In the
following, let v be a free node if v does not have a server. Roughly, at the beginning of a phase i, we choose a
set Ni of ni (ideally) free nodes and make sure that all these nodes have Γi requests. Note that constructing an
execution means to determine where to add the request in each iteration. The value Γi is chosen large enough
such that throughout phase i a service cost of ni Γi is sufficiently large to force an algorithm to move. Hence,
whenever there are ni free nodes with Γi requests, A has to move at least one server to one of these nodes.
For each such movement, we pick another free node that currently has less than Γi requests and make sure it
has Γi requests. We proceed until there are k nodes with Γi requests at which point the main part of the phase
ends. Except for the nodes in Ni , each of the k nodes with Γi requests leads to a movement of A and therefore,
A has to move at least k − ni = Ω(k) servers in phase i. At the end of phase i, we can guarantee that there
are exactly k nodes with Γi requests, ni nodes with Γi−1 requests, ni−1 − ni nodes with Γi−2 requests, etc.
Assuming P
that for all v, σv (x, y) = (1 − x)y, we can then compute the optimal service cost after phase p as
np Γp−1 + pi=3 (ni−1 − ni )Γi−2 . The service cost paid by A at time t can not be smaller than St∗ . By contrast,
the optimal offline algorithm moves at most ni−1 − ni + 1 times in each phase i > 1 (in the first phase it moves
just once) and at most np at the end of the last phase to locate its servers in the optimal configuration. Therefore
19

by the end of phase p, O has to pay at most O(n1 + p) as the total movement cost. If we choose p ≥ k, the total
movement cost paid by O is O(p) by end of phase p, while the online algorithm has to pay Θ(pk) in total by
this time. The service cost of O equals the optimal service cost at the end of phase p. By choosing the values
ni appropriately, we obtain the claimed bounds.
5.4.1

Lower Bound Execution

We need n to be sufficiently large, for simplicity assume that n ≥ 3k. As we can assume that each node either
has 0 or 1 server, we slightly overload notation and simply denote a feasible configuration by a set F ⊂ V of
size |F | = k. Further, we assume all servers are at the same locations at the beginning (i.e. t = 0) without loss
of generality. At each point t in the execution, an optimal configuration Ft∗ places servers at the k nodes with
the most requests (breaking ties arbitrarily if there are several nodes with the same number of requests). Also,
at a time t the optimal service cost is equal to the total number of requests at nodes in V \ Ft∗ for an arbitrary
optimal configuration Ft∗ .
Time is divided into phases. We construct the execution such that it lasts for at least k phases. As described
in the outline, we define integers Γ1 < Γ2 < . . . such that at the end of phase i, there are exactly k nodes with
Γi requests (and all other nodes have fewer requests). For each phase i, we define Vi to be this set of k nodes
with Γi requests. We also fix integers k/3 ≥ n1 ≥ n2 ≥ · · · ≥ 1 and at the beginning of each phase i, we pick
a set Ni of ni nodes to which we directly add requests so that all of them have exactly Γi requests. For i = 1,
we pick N1 as an arbitrary subset of V \ F0 . We define V0 := F0 . For i ≥ 2, we choose Ni as an arbitrary
subset of Vi−2 \ Vi−1 . Clearly, at the end of phase i, we have Ni ⊆ Vi as otherwise there would be more than
k nodes with exactly Γi requests. Note that because Ni−1 ⊆ Vi−1 and because Ni−1 ∩ Vi−2 = ∅, Vi−2 \ Vi−1
contains ni−1 ≥ ni nodes and it is therefore possible to choose Ni as described. Note also that because
Ni ⊆ Vi−2 \ Vi−1 , at the beginning of phase i all nodes in Ni have exactly Γi−2 requests. The remaining ones
of the k nodes that end up in Vi (and thus have Γi requests at the end of phase i) are chosen among the nodes
in Vi−1 . Consequently, at the end of phase i − 1 and thus at the beginning of phase i, there are exactly k nodes
Vi−1 with Γi−1 requests, ni−1 nodes Vi−2 \ Vi−1 with Γi−2 requests, ni−2 − ni−1 requests Vi−3 \ (Vi−2 ∪ Ni−1 )
with Γi−3 requests, ni−3 − ni−2 nodes with Γi−4 requests, and so on. Now, ni of the nodes in Vi−2 \ Vi−1 are
chosen as set Ni and we increase their number of requests to Γi . From now on, throughout phase i, there are
k + ni nodes with at least Γi−1 requests such that at most k of these nodes have Γi requests. The number of
nodes with less than Γi−1 requests is the same as at the end of phase i−1. In fact nodes that are not in Vi−1 ∪Ni
do not change their number of requests after phase i − 1. As a consequence of the execution, after increasing
the number of requests in Ni to Γi , the optimal service cost remains constant throughout phase i ≥ 1 and it can
be evaluated to
i−1
X
(nj − nj+1 )Γj−1 .
Σ∗i := ni · Γi−1 +
j=2

For convenience, we also define Σ∗0 := 0 and moreover Σ∗1 = 0 since there are at most k nodes with Γ1 requests
at the end of phase 1.
In the following, let v be a free node at some point in the execution, if the algorithm currently has no server
at node v. We now fix a phase p ≥ 1 and assume that we are at a time t, when we have already picked the set
Np and increased the number of requests of nodes in Np to Γp . By the above observation, we have St∗ = Σ∗p
and therefore A is forced to move if there are np free nodes with Γp requests and if we choose Γp such that
γp := Γp − Γp−1

(α − 1)Σ∗p + β
.
=
np

(47)

We can now describe how and when the remaining k − np nodes of Vp are chosen after picking the nodes in Np .
As described above, the nodes are chosen from Vp−1 . We choose the nodes sequentially. Whenever we choose
a new node from Vp , we pick some free node v ∈ Vp−1 with less than Γp requests and increase the number
of requests of v to Γp . As described above, Γp is chosen large enough (as given in (47)) such that throughout
20

phase p there are never more than np − 1 free nodes with Γp requests. Because |Np ∪ Vp−1 | = k + np , as long
as there are at most k nodes with Γp requests there always needs to be a free node v ∈ Vp−1 that we can pick
and we actually manage to add k nodes to Vp .
5.4.2

Online Algorithm Total Cost

The service cost paid by A at any time t could be simply lower bounded by St∗ . Hence, it remains to compute a
lower bound for MtA as a function of optimal service cost. The following lemma computes such a lower bound.
Lemma 5.10. For any α ≥ 1 and β satisfying (1), assume A be any deterministic online algorithm that can
solve the problem. There exists a time t > 0 such that the execution of Section 5.4.1 guarantees the total
movement cost MtA can be bounded as follows.
• If α = 1, for any ℓ ≥ 1, ε > 0, and β ≤ k(2k)1/ℓ /ε, we have

MtA = ε · St∗ + Θ(ℓk).

Specifically, for β = O(k + k/ε) we get MtA = ε · St∗ + Θ(k log k) and for β = O
k log k 
MtA = ε · St∗ + Θ log
log k .

k log k 
log log k

we have

• For α ≥ 1 + ε where ε > 0 is some constant and any β satisfying (1), we have
MtA = k · Θ (1 + logα St∗ ) .

Proof. Let us count the number of movements of A in a given phase p. At each point in time t during the
phase, let Φt be the number of free nodes with Γp requests (possibly including a node v that we already chose
to be added to Vp ). We know that for all t, Φt < np . Whenever we decide to add a new node v to Vp , Φt
increases by 1 (as v is a free node). The value of Φt can only decrease when A moves a server and each server
movement reduces the value of Φt by at most 1. As after fixing Np , we add k − np nodes to Vp , we need at least
k − 2np ≥ k/3 movements to keep Φt below np throughout the phase. Consequently, every online algorithm
A has to do at least k/3 movements in each phase.
Now we upper bound the optimal service cost Σ∗p as a function of α, β, and p. Using (47), for all p ≥ 0, we
have
p
X
np · γp−1
Σ∗p =
i=1

For p ≥ 1, we then get


np
(α − 1)Σ∗p−1 + β + Σ∗p−1
np−1


(48)
np
np
= 1 + (α − 1)
.
· Σ∗p−1 + β ·
np−1
np−1
In the following, we for simplicity assume that for i = 1, 2, . . . , p, values ni do not have to be integers. For
integer ni , the proof works in the same way, but becomes more technical and harder to read. We fix the values
of ni as
p−i
ni := (k/3) p−1
Σ∗p =

1

i
= ( k3 )− p−1 . Equation (48) now be simplified
such that n1 = k/3 and np = 1. For all i ≥ 1, we then have nin−1
as


1
α−1
∗
· Σ∗p−1 + β ·
.
(49)
Σp = 1 +
1/(p−1)
1/(p−1)
(k/3)
(k/3)
We have already seen that St∗ = Σ∗p . Using (49) and (33), the claim of the first part of the lemma follows
analogously from Lemma 5.4 and Lemma 5.6 and the claim of the second part of the lemma follows analogously
from Lemma 5.4 and Lemma 5.7 in the upper bound analysis section.

21

5.4.3

Optimal Offline Algorithm Total Cost

First we specify a specific offline algorithm A and compute its total cost. It is obvious that
A
Cost O
t ≤ Cost t

(50)

for every time t. The offline algorithm A knows the request sequence in advance as well as everything about
A in order to answer each request. When Algorithm A moves a server, it always moves a server from a node
with a minimum number of requests to a node with a maximum number of requests (among the nodes where
A did not have a server before the movement). We show that Algorithm A always satisfies (2) and that the
number of movements is sufficiently small.
Offline Algorithm A : With respect to the execution described in Section 5.4.1, at the beginning of the first
phase, the offline algorithm moves one server from (FtA0 \ V1 ) to a node in (V1 \ FtA0 ). For i ≥ 2, at the
beginning of each phase i, it moves all servers located at nodes in (FtAi−1 \ Vi ) that have less than Γi−1 requests
to some nodes in (Vi \ FtAi−1 ). Further, among the servers located at nodes in (FtAi−1 \ Vi ) and which have Γi−1
requests, Algorithm A moves as few servers as possible to nodes in (Vi \ FtAi−1 ) such that the number of nodes
with Γi requests and without servers (of A ) becomes less than ni . At the end of the execution, the offline
algorithm moves all its servers to the locations of an optimal configuration. Therefore, the service cost paid by
the offline algorithm at the end of the execution equals the optimal service cost, i.e.,
StAp = St∗p .

(51)

Correctness of the Offline Algorithm A : We show that the offline algorithm A keeps (2) satisfied at all
times. Regarding to the algorithm, at the end of each phase i ≥ 1 we have xi < ni nodes in (Vi \ FtAi ).
Moreover, xi servers of A that are in (FtAi \ Vi ) are at nodes with Γi−1 requests. Therefore we have
StAi

≤

=

(47)

=

xi <ni

<

xi · Γi + St∗i − xi · Γi−1

xi · (Γi − Γi−1 ) + St∗i
(α − 1) · St∗i + β
+ St∗i
ni /xi
α · St∗i + β.

Since the offline algorithm moves its servers at the beginning of phase i, at all times within phase i, Condition
(2) remains satisfied.
The following lemma shows that the number of movements by the offline algorithm A is at most k/3 + p
where p is the number of phases of the execution provided in Section 5.4.1.
Lemma 5.11. For any α ≥ 1 and β satisfying (1), the execution of Section 5.4.1 consisting of p phases provides
MtA <

k
+ p,
3

where t is the ending time of phase p.
Proof. Let ti denote the ending time of phase i. The following claim guarantees that the number of movements
at each iteration i for A to keep (2) satisfied is sufficiently small. More specifically, at the beginning of phase
i, the offline algorithm moves in two steps. The first step is when it moves its servers from the nodes with less
than Γi−1 requests. The first part of the following claim guarantees that the number of these movements is at
most ni−1 − ni . The second step is done when all servers of A are at the nodes with either Γi or Γi−1 requests.
The second part of the following claim indicates that after the first step is done by the offline algorithm, there
remain at most ni nodes with Γi requests and without any server of the offline algorithm.
22

Claim 5.12. For i ≥ 2,

A \ (V
(1) |Fi−1
i−1 ∪ Vi )| ≤ ni−1 − ni .

A | ≤ |F A \ (V
(2) |Vi \ Fi−1
i−1 ∪ Vi )| + ni .
i−1

Proof. At the end of phase (i − 1), for i ≥ 2, we have ni−1 = |Vi−2 \ Vi−1 | where each of the nodes
in (Vi−2 \ Vi−1 ) has Γi−2 requests. Assume wi of them are with the servers of the offline algorithm.
Therefore, (k − wi ) of the nodes in Vi−1 are with the servers of A . During phase i, a set of Ni ⊆
(Vi−2 \ Vi−1 ) is chosen (|Ni | = ni ) and the number of requests at them increased to Γi . There are two
cases: either ni ≤ (ni−1 − wi ) or ni > (ni−1 − wi ). In both cases, there are at most (ni−1 − ni ) nodes
with Γi−2 requests that are with servers of the offline algorithm. Hence, the first part of the claim holds.
As already described, there are (k − wi ) nodes in (FtAi−1 \ Vi−1 ). With respect to the execution, the
requests at (k−ni ) nodes in Vi−1 increased to Γi since the execution has to guarantee that there are exactly
k nodes with Γi requests at the end of phase i. Hence, at most wi nodes in Vi−1 can have Γi requests while
A ) in which
are without any server of A . If ni > (ni−1 − wi ) then we have at most ni−1 nodes in (Vi \ Fi−1
at most (ni−1 − wi ) of them are among the nodes in (Vi−2 \ Vi−1 ). Since the number of nodes with Γi−2
requests with servers of the offline algorithm is at most (ni−1 − ni ), therefore the second part holds for
A ) in which
this case. Otherwise, if ni ≤ (ni−1 − wi ) then we have at most (ni + wi ) nodes in (Vi \ Fi−1
at most ni of them are among the nodes in (Vi−2 \ Vi−1 ). Since the number of nodes with Γi−2 requests
with servers of the offline algorithm is at most wi , hence the second part holds as well for this case.
At the beginning of the first phase, the offline algorithm moves one server. For i ≥ 2, it follows from to
the offline algorithm description and the first part of the Claim 5.12 that the offline algorithm moves at most
(ni−1 − ni ) times at the beginning of each phase i. Therefore using the second part of the claim, the number of
nodes with Γi requests and without any server of A is at most ni . If it is strictly less than ni then A does not
move anymore due to the description of the offline algorithm. Otherwise, the number of nodes with Γi requests
A \ (V
and without any server of A is ni after moving the servers in (Fi−1
i−1 ∪ Vi )). This implies that the number
of nodes with Γi−1 requests and with servers of A is ni . Hence, the offline algorithm needs to move only one
server that is located at a node with Γi−1 requests to a node with Γi requests and without any server of the
offline algorithm to keep the number of nodes with Γi requests and without any server of A below ni . At the
end of the execution that is the end of phase p, the number of nodes with Γp−1 requests and with servers of
A is at most (np − 1) because the number of nodes in (Vp \ FtAp ) is less than np . Thus, as described in the
algorithm, the offline algorithm moves at most (np − 1) times to locate its all servers at the nodes with optimal
servers in Ft∗p so that provides the optimal total service cost. Consequently, the total number of movements by
A is at most
!
p
X
n1 ≤k/3
k
(ni−1 − ni + 1) + (np − 1) ≤ p − 1 + .
1+
3
i=2

Corollary 5.13. With respect to (50), (51), and the Lemma 5.11 we can get
A
∗
Cost O
t ≤ Cost t ≤ St +

4·p
.
3

since p ≥ k and t is the ending time of the execution.
Proof of Theorem 3.3. By Lemma 5.10 and the Corollary 5.13 the claim of the theorem holds.

23

6

Future Work

A possible way to extend the work of this paper could be to study an online version of MFLP [11] (OMFLP). In
[4], it is shown that exploiting the randomized low-stretch hierarchical tree decomposition of [9], it is possible to
obtain a polylogarithmic competitive ratio for the k-server problem. Combined with the general cost functions
studied in the present paper, a similar approach could work for OMFLP. On each level of the hierarchical
decomposition, the cost of each subtree can potentially be modelled using a cost function similar to what we
use in the present paper. Note that the lower bound of Theorem 3.3 already applies to OMFLP, even for a
uniform underlying metric. Another natural direction would be to study randomized online algorithms for
minimizing the movements in our model against an oblivious adversary.

References
[1] S. Ahmadian, Z. Friggstad, and C. Swamy. Local-search based approximation algorithms for mobile facility location problems. In Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 1607–1621, 2013.
[2] S. Arora, E. Hazan, and S. Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(1):121–164, 2012.
[3] V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, and V. Pandit. Local search heuristics for
k-median and facility location problems. SIAM Journal on Computing, 33(3):544–562, 2004.
[4] N. Bansal, N. Buchbinder, A. Madry, and J. S. Naor. A polylogarithmic-competitive algorithm for the
k-server problem. In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer
Science (FOCS), pages 267–276, 2011.
[5] J. Byrka and K. Aardal. An optimal bifactor approximation algorithm for the metric uncapacitated facility
location problem. SIAM Journal on Computing, 39(6):2212–2231, 2010.
[6] M. Charikar, C. Chekuri, T. Feder, and R. Motwani. Incremental clustering and dynamic information
retrieval. In Proceedings of the 29th Annual ACM Symposium on Theory of computing (STOC), pages
626–635, 1997.
[7] E. D. Demaine, M. Hajiaghayi, H. Mahini, A. S. Sayedi-Roshkhar, S. Oveisgharan, and M. Zadimoghaddam. Minimizing movement. ACM Transactions on Algorithms (TALG), 5(3):30, 2009.
[8] Z. Drezner and H. W. Hamacher. Facility Location: Applications and Theory. Springer Science &
Business Media, 2004.
[9] J. Fakcharoenphol, S. Rao, and K. Talwar. A tight bound on approximating arbitrary metrics by tree
metrics. In Proceedings of the 35th Annual ACM Symposium on Theory of computing (STOC), pages
448–455, 2003.
[10] D. Fotakis. Online and incremental algorithms for facility location. ACM SIGACT News, 42(1):97–131,
2011.
[11] Z. Friggstad and M. R. Salavatipour. Minimizing movement in mobile facility location problems. ACM
Transactions on Algorithms (TALG), 7(3):28, 2011.
[12] S. Guha and S. Khuller. Greedy strikes back: improved facility location algorithms. In Proceedings of
the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 649–657, 1998.
[13] M. T. Hajiaghayi, M. Mahdian, and V. S. Mirrokni. The facility location problem with general cost
functions. Networks, 42(1):42–47, 2003.
24

[14] K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. V. Vazirani. Greedy facility location algorithms
analyzed using dual fitting with factor-revealing LP. Journal of the ACM (JACM), 50(6):795–824, 2003.
[15] E. Koutsoupias and C. H. Papadimitriou. On the k-server conjecture. Journal of the ACM (JACM),
42(5):971–983, 1995.
[16] N. Littlestone and M. K. Warmuth. The weighted majority algorithm. Information and computation,
108(2):212–261, 1994.
[17] M. S. Manasse, L. A. McGeoch, and D. D. Sleator. Competitive algorithms for server problems. Journal
of Algorithms, 11(2):208–230, 1990.
[18] A. Meyerson. Online facility location. In Proceedings of the 42nd IEEE Symposium on Foundations of
Computer Science (FOCS), page 426, 2001.
[19] S. Shalev-Shwartz. Online learning and online convex optimization. Foundations and Trends in Machine
Learning, 4(2):107–194, 2011.
[20] D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications of
the ACM, 28(2):202–208, 1985.

25

