An O(log k log2 n)-competitive Randomized Algorithm for the
k-Sever Problem

arXiv:1510.07773v1 [] 27 Oct 2015

Wenbin Chen∗†‡

Abstract
In this paper, we show that there is an O(log k log2 n)-competitive
randomized algorithm for the k-sever problem on any metric space
with n points, which improved the previous best competitive ratio
O(log2 k log3 n log log n) by Nikhil Bansal et al. (FOCS 2011, pages 267276).
Keywords: k-sever problem; Online algorithm; Primal-Dual method;
Randomized algorithm;

1

Introduction

The k-sever problem is to schedule k mobile servers to serve a sequence of requests in a metric
space with the minimum possible movement distance. In 1990, Manasse et al. introduced the ksever problem as a generalization of several important online problems such as paging and caching
problems [29] ( Its conference version is [28]), in which they proposed a 2-competitive algorithm
for the 2-sever problem and a n − 1-competitive algorithm for the n − 1 sever problem in a n-point
metric space. They still showed that any deterministic online algorithm for the k-sever problem is
of competitive ratio at least k. They proposed the well-known k-sever conjecture: for the k-sever
problem on any metric space with more than k different points, there exists a deterministic online
algorithm with competitive ratio k.
It was in [29] shown that the k-sever conjecture holds for two special cases: k = 2 and n = k + 1.
The k-sever conjecture also holds for the k-sever problem on a uniform metric. The special case
of the k-sever problem on a uniform metric is called the paging (also known as caching) problem.
Slator and Tarjan have proposed a k-competitive algorithm for the paging problem [31]. For some
other special metrics such as line, tree, there existed k-competitive online algorithms. Yair Bartal
∗

Email:cwb2011@gzhu.edu.cn
Department of Computer Science, Guangzhou University, P.R. China
‡
State Key Laboratory for Novel Software Technology, Nanjing University, P.R. China

†

1

and Elias Koutsoupias show that the Work Function Algorithm for the k-sever problem is of kcompetitive ratio in the following special metric spaces: the line, the star, and any metric space
with k + 2 points [16]. Marek Chrobak and Lawrence L. Larmore proposed the k-competitive
Double-Coverage algorithm for the k-sever problem on trees [21].
For the k-sever problem on the general metric space, the k-sever conjecture remain open. Fiat
et al. were the first to show that there exists an online algorithm of competitive ratio that depends
only on k for any metric space: its competitive ratio is Θ((k!)3 ). The bound was improved later
by Grove who showed that the harmonic algorithm is of competitive ratio O(k2k ) [25]. The result
was improved to (2k log k) by Y.Bartal and E. Grove [14]. A significant progress was achieved by
Koutsoupias and Papadimitriou, who proved that the work function algorithm is of competitive
ratio 2k − 1 [27].
Generally, people believe that randomized online algorithms can produce better competitive
ratio than their deterministic counterparts. For example, there are several O(log k)-competitive
algorithms for the paging problem and a Ω(log k) lower bound on the competitive ratio in [24, 30,
1, 4]. Although there were much work [17, 13, 15], the Ω(log k) lower bound is still best lower bound
in the randomized case. Recently, N. Bansal et al. propose the first polylogaritmic-competitive
randomized algorithm for the k-sever problem on a general metrics spcace [3]. Their randomized
algorithm is of competitive ratio O(log2 k log3 n log log n) for any metric space with n points, which
improves on the deterministic 2k − 1 competitive ratio of Koutsoupias and Papadimitriou whenever
n is sub-exponential k.
For the k-server problem on the general metric space, it is widely conjectured that there is an
O(log k)-competitive randomized algorithm, which is called as the randomized k-server conjecture.
For the paging problem ( it corresponds to the k-sever problem on a uniform metric), there is
O(log k)-competitive algorithms [24, 30, 1]. For the weighted paging problem ( it corresponds to the
k-sever problem on a weighted star metric space), there were also O(log k)-competitive algorithms
[4, 9] via the online primal-dual method. More extensive literature on the k-server problem can be
found in [26, 18].
In this paper, we show that there exists a randomized k-sever algorithm of O(log k log2 n)competitive ratio for any metric space with n points, which improved the previous best competitive
ratio O(log2 k log3 n log log n) by Nikhil Bansal et al. [3].
In order to get our results, we use the online primal-dual method, which is developed by Buchbinder and Naor et al. in recent years. Buchbinder and Naor et al. have used the primal-dual
method to design online algorithms for many online problems such as covering and packing problems, the ad-auctions problem and so on [4, 5, 6, 7, 8, 10]. First, we propose a primal-dual
formulation for the fraction k-sever problem on a weighted hierarchical well-separated tree (HST).
Then, we design an O(ℓ log k)-competitive online algorithm for the fraction k-sever problem on a
weighted HST with depth ℓ. Since any HST with n leaves can be transformed into a weighted
HST with depth O(log n) with any leaf to leaf distance distorted by at most a constant [3], thus,
we get an O(log k log n)-competitive online algorithm for the fraction k-sever problem on an HST.
Based on the known relationship between the fraction k-sever problem and the randomized k-sever
problem, we get that there is an O(log k log n)-competitive randomized algorithm for the k-sever
problem on an HST with n points. By the metric embedding theory [22], we get that there is an
O(log k log2 n)-competitive randomized algorithm for the k-sever problem on any metric space with
n points.

2

2

Preliminaries

In this section, we give some basic definitions.
Definition 2.1. (Competitive ratio adapted from [32]) For a deterministic online algorithm DALG,
we call it r-competitive if there exists a constant c such that for any request sequence ρ, costDALG (ρ) ≤
r · costOP T (ρ) + c, where costDALG (ρ) and costOP T (ρ) are the costs of the online algorithm DALG
and the best offline algorithm OP T respectively.
For a randomized online algorithm, we have a similar definition of competitive ratio:
Definition 2.2. (Adapted from [32]) For a randomized online algorithm RALG, we call it rcompetitive if there exists a constant c such that for any request sequence ρ, E[costRALG (ρ)] ≤
r · costOP T (ρ) + c, where E[costRALG (ρ)] is the expected cost of the randomized online algorithm
RALG.
In order to analyze randomized algorithms for the k-sever problem, D. Türkouğlu introduce the
fractional k-sever problem [32]. On the fractional k-sever problem, severs are viewed as fractional
entities as opposed to units and an online algorithm can move fractions of servers to the requested
point.
Definition 2.3. (Fractional k-sever problem adapted from [32]) Suppose that there are a metric
space S and a total of k fractional severs located at the points of the metric space. Given a sequence
of requests, each request must be served by providing one unit server at requested point, through
moving fractional servers to the requested point. The cost of an algorithm for servicing a sequence
of requests is the cumulative sum of the distance incurred by each sever, where moving a w fraction
of a server for a distance of δ costs wδ.
In [11, 12], Bartal introduce the definition of a Hierarchical Well-Separated Tree (HST), into
which a general metric can be embedded with a probability distribution. For any internal node, the
distance from it to its parent node is σ times of the distance from it to its child node. The number
σ is called the stretch of the HST. An HST with stretch σ is called a σ-HST. In the following, we
give its formal definition.
Definition 2.4. (Hierarchically Well-Separated Trees (HSTs)[20]). For σ > 1, a σ-Hierarchically
Well-Separated Tree (σ-HST) is a rooted tree T = (V, E) whose edges length function d satisfies the
following properties:
(1). For any node v and any two children w1 , w2 of v, d(v, w1 ) = d(v, w2 ).
(2). For any node v, d(p(v), v) = σ · d(v, w), where p(v) is the parent of v and w is a child of v.
(3). For any two leaves v1 and v2 , d(p(v1 ), v1 ) = d(p(v2 ), v2 ).
Fakcharoenphol et al. showed the following result [22].
Lemma 2.5. If there is a γ-competitive randomized algorithm for the k-sever problem on an σ-HST
with all requests at the n leaves, then there exists an O(γσ log n)- competitive randomized online
algorithm for the k-server problem on any metric space with n points.
We still need the definition of a weighted hierarchically well-separated tree introduced in [3].

3

Definition 2.6. (Weighted Hierarchically Well-Separated Trees (Weighted HSTs)[3]). A weighted
σ-HST is a rooted tree satisfying the property (1), (3) of the definition 2.4 and the property:
d(p(v), v) ≥ σ · d(v, w) for any node v which is not any leaf or the root, where p(v) is the parent of v and w is a child of v.
In [3], Banasl et al. show that an arbitrary depth σ-HST with n leaves can be embedded into
an O(log n) depth weighted σ-HST with constant distortion, which is described as follows.
Lemma 2.7. Let T be a σ-HST T with n leaves which is of possibly arbitrary depth. Then, T can
be transformed into a weighted σ-HST T̃ with depth O(log n) such that: the leaves of T̃ and T are
2σ
factor.
the same, and leaf to leaf distance in T is distorted in T̃ by a at most σ−1

3

An O(log2 k) Randomized Algorithm for the k-Sever Problem on
an HST when n = k + 1

In this paper, we view the k-sever problem as the weighed caching problem such that the cost of
evicting a page out of the cache using another page satisfies the triangle inequality, i.e., a point is
viewed as a page; the set of k points that are served by k severs is viewed as the cache which holds
k pages; the distance of two points i and j is viewed the cost of evicting the corresponding page pi
out of the cache using the corresponding page pj .
Let [n] = {p1 , . . . , pn } denotes the set of n pages and d(pi , pj ) denotes the cost of evicting
the page pi out of the cache using the page pj for any pi , pj ∈ [n], which satisfies the triangle
inequality: for any pages i, j, s, d(pi , pi ) = 0; d(pi , pj ) = d(pj , pi ); d(pi , pj ) ≤ d(pi , ps ) + d(ps , pj ).
Let p1 , p2 , . . . , pM be the requested pages sequence until time M , where pt is the requested page at
time t. At each time step, if the requested page pt is already in the cache then no cost is produced.
Otherwise, P
the page pt must be fetched into the cache by evicting some other pages p in the cache
and a cost
d(p, pt ) is produced.
In this section, in order to clearly describe our algorithm design idea, we consider the case
n = k + 1.
First, we give some notations. Let σ-HST denote a hierarchically well-separated trees with
stretch factor σ. Let N be the number of nodes in a σ-HST and leaves be p1 , p2 , · · · , pn . Let ℓ(v)
denote the depth of a node v. Let r denote the root node. Thus, ℓ(r) = 0. For any leaf p, let ℓ
denote its depth, i.e. ℓ(p) = ℓ. Let p(v) denote the parent node of a node v. C(v) denote the set
of children of a node v. Let D denote the distance from the root to its a child. D(v) denote the
D
.
distance from a node v to its parent, i.e. D(v) = d(v, p(v)). It is easy to know that D(v) = σℓ(v)−1
Let Tv denote the subtree rooted at v and L(Tv ) denote the set of leaves in Tv . Let |Tv | denote the
number of the leaves in Tv . For a leaf pi , let A(pi , j) denote the ancestor node of pi at the depth
j. Thus, A(pi , ℓ) is pi , A(pi , 0) is the root r and so on. At time t, let variable xpi ,t denote the
fraction of pi that is in
Pthe cache and upi ,t denote the fraction
Pof pi that is out of cache. Obviously,
xpi ,t + upi ,t = 1 and
xp,t = k. For a node v, let uv,t =
up,t , i.e., it is the total fraction of
p∈[n]
p∈L(Tv )
P
pages in the subtree Tv which is out of the cache. It is easy to see that uv,t =
uw,t. Suppose
w∈C(v)

that at time 0, the set of initial k pages in the cache is I = {pi1 , . . . , pik }.
At time t, when the request pt arrives, if page pt is fetched mass ∆(pt , p) into the cache by
evicting out the page p in the cache, then the evicting cost is d(p, pt ) · ∆(pt , p). For a σ-HST metric,
4

suppose the path from pt to p in it is: pt , vj , . . . , v1 , v, v1′ , . . . , vj′ , p, where v is the first common
ancestor node of pt and p. By the definition of a σ-HST, we have D(pt ) = D(p) and D(vi ) = D(vi′ )
j
j
j
P
P
P
for any 1 ≤ i ≤ j. Thus, d(p, pt ) = D(pt ) +
D(vi ) + D(p) +
D(vi′ ) = 2D(pt ) +
2D(vi ). So,
the evicting cost is (2D(pt )+
cost incurred at time t is

N
P

j
P

i=1

i=1

i=1

2D(vi ))·∆(pt , p). Since p can be any page in [n]\{pt }, the evicting

i=1

2D(v) max{0, uv,t−1 − uv,t }. Thus, we give the LP formulation for the

v=1

fractional k-sever problem on a σ-HST as follows.
M P
N
M
P
P
(P)
Minimize
2D(v)zv,t +
∞ · upt ,t
t=1 v=1
t=1 P
up,t ≥ |S| − k;
Subject to ∀t > 0 and S ⊆ [n] with |S| > k,
p∈S
P
(up,t−1 − up,t );
∀t > 0 and a subtree Tv (v 6= r), zv,t ≥

(3.1)
(3.2)

p∈L(Tv )

∀t > 0 and node v, zv,t , uv,t ≥ 0;
(3.3)
For t = 0 and any leaf node p ∈ I, up,0 = 0;
(3.4)
For t = 0 and any leaf node p 6∈ I, up,0 = 1;
(3.5)
The first primal
constraintP
(3.1) states that
Pat any time t, if we take any set S of vertices with
P
xp,t = |S| − k, i.e., the total number of pages out
xp,t ≥ |S| −
up,t = |S| −
|S| > k, then
p∈S

p∈S

p∈[n]

of the cache is at lease |S| − k. The variables zv,t denote the total fraction mass of pages in Tv that
are moved out of the subtree Tv (Obviously, it is not needed to define a variable zr,t for the root
node). The fourth and fifth constraints ((3.4) and (3.5)) enforce the initial k pages in the cache
are pi1 , . . . , pik . The first term in the object function is the sum of the moved cost out of the cache
and the second term enforces the requirement that the page pt must be in the cache at time t (i.e.,
upt ,t = 0).
Its dual formulation is as follows.
M
P
P
P
γp
(|S| − k)aS,t +
(D)
Maximize
t=1 S⊆[n],|S|>k

Subject to ∀t and p ∈ [n] \ {pt },

p6∈I

P

aS,t −

S:p∈S

∀t = 0 and ∀p ∈ [n], γp −

ℓ
P

ℓ
P

(b(A(p,j),t+1 − b(A(p,j),t ) ≤ 0

(3.6)

j=1

bA(p,j),1 ≤ 0

(3.7)

j=1

∀t > 0 and any subtree Tv , bv,t ≤ 2D(v)
(3.8)
∀t > 0 and v and |S| > k, aS,t , bv,t ≥ 0
(3.9)
In the dual formulation, the variable aS,t corresponds to the constraint of the type (3.1); the
variable bv,t corresponds to the constraint of the type (3.2); The variable γp corresponds to the
constraint of the type (3.4) and (3.5).
Based on above primal-dual formulation, we extend the design idea of Bansal et al.’s primaldual algorithm for the metric task system problem on a σ-HST [10] to the k-sever problem on a
σ-HST. The design idea of our online algorithm is described as follows. During the execution of
our algorithm, it always maintains the following relation between the primal variable uv,t and dual
bv,t+1
ln(1 + k)) − 1). When the request pt arrives at
variable bv,t+1 : uv,t = f (bv,t+1 ) = |Tkv | (exp( 2D(v)
time t, the page pt is gradually fetched into the cache and other pages are gradually moved out of
5

the cache by some rates until pt is completely fetched into the cache(i.e, upt ,t is decreased at some
rate and other up,t is increased at some rate for any p ∈ [n] \ {pt } until upt ,t becomes 0). It can be
viewed that we move mass upt ,t out of leaf pt through its ancestor nodes and distribute it to other
leaves p ∈ [n] \ {pt }. In order to compute the exact distributed amount at each page p ∈ [n] \ {pt },
the online algorithm should maintain the following invariants:
1. ( Satisfying Dual Constraints:) It is tight for all dual constraints of type (3.6) on other
leaves [n] \ {pt }.
P
2. (Node Identity Property:) uv,t =
uw,t holds for each node v,.
w∈C(v)

We give more clearer description of the online algorithm process. At time t, when the request
pt arrives, we initially set upt ,t = upt ,t−1 . If upt ,t = 0, then we do nothing. Thus, the primal cost
and the dual profit are both zero. All the invariants continue to hold. If upt ,t 6= 0, then we start
to increase variable aS at rate 1. At each step, we would like to keep the dual constraints (3.6)
tight and maintain the node identity property. However, increasing variable aS violates the dual
constraints(3.6) on leaves in [n] \ {pt }. Hence, we increase other dual variables in order to keep
these dual constraints (3.6) tight. But, increasing these variables may also violate the node identity
property. So, it makes us to update other dual variables. This process results in moving initial upt ,t
mass from leaf pt to leaves [n] \ {pt }. We stop the updating process when upt ,t become 0.
In the following, we will compute the exact rate at which we should move mass upt ,t from pt
through its ancestor nodes at time t to other leaves in [n] \ {pt } in the σ-HST. Because of the space
limit, we put proofs of the following some claims in the Appendix. First, we show one property of
the function f .
Lemma 3.1.

duv,t
dbv,t+1

Proof. Since uv,t =
claim.

=

ln(1+k)
2D(v) (uv,t

bv,t+1
|Tv |
k (exp( 2D(v)

+

|Tv |
k ).

ln(1 + k)) − 1), we take the derivative over bv,t+1 and get the

In order to maintain the Node Identity Property: uv,t =

P

uw,t for each node v at any

w∈C(v)

time t, when uv,t is increased or decreased, it is also required to increase or decrease the children
of v at some rate. The connection between these rates is given.
Lemma 3.2. For a node v, if we increase variable bv,t+1 at rate h, then we have the following
equality:
P dbw,t+1
dbv,t+1
|Tv |
1
=
· (uw,t + |Tkv | )
σ (uv,t + k ) ·
dh
dh
w∈C(v)

We need one special case of lemma 3.2: when the variable bv,t+1 is increased (decreased) at rate
h, it is required that the increasing (decreasing) rate of all children of v is the same. By above
lemma, we get:
Lemma 3.3. For v a node, assume that we increase (or decrease ) the variable bv,t+1 at rate h. If
the increasing (or decreasing ) rate of each w ∈ C(v) is the same, then in order to keep the Node
Identity Property, we should set the increasing (or decreasing ) rate for each child w ∈ C(v) as
follows:
db
dbw,t+1
= σ1 · v,t+1
dh
dh
Repeatedly applying this lemma, we get the following corollary.
6

Corollary 3.4. For a node v with ℓ(v) = j and a path P from leaf pi ∈ Tv to v, if bv,t+1 is increased
( or decreased) at rate h and the increasing (decreasing) rate of all children of any v ′ ∈ P is the
P dbv′ ,t+1
db
1
) = (1 + Θ( σ1 )).
= v,t+1
· ψ(j), where ψ(j) = (1 + σ1 + σ12 + · · · + σℓ−j
same, then
dh
dh
v′ ∈P

We still require the following special case of lemma 3.2. Let w1 be the first child of the node
v. Assume that bw1 ,t+1 is increased (or decreased) at some rate and the rate of increasing (or
decreasing) bw′ ,t+1 is the same for every w′ ∈ C(v), w′ 6= w1 . If bv,t+1 is unchanged, then the
following claim should hold.
Lemma 3.5. Let w1 , . . . , wm be the children of a node v. Assume that we increase (or decrease)
db ′
db i ,t+1
w1 at rate h and also increase w2 to wm at the same rate h. For i ≥ 2, let wdh,t+1 be wdh
. If
we would like to maintain the amount uv,t unchanged, then we should have:
dbw′ ,t+1
dh

|T (w1 )|
k
|T (v)|
uv,t + k

uw1 ,t +

=

· (−

dbw1 ,t+1
dh

+

dbw′ ,t+1
)
dh

Theorem 3.6. When request pt arrives at time t, in order to keep the dual constraints tight
and node identity property, if aS,t is increased with rate 1, we should decrease every bA(pt ,j),t+1
(1 ≤ j ≤ ℓ) with rate:
dbA(pt ,j),t+1
daS,t

2+

1

|T

|T

|

|

n−1
= ψ(j)
[(uA(pt ,j),t + A(pk t ,j) )−1 − (uA(pt ,j−1),t + A(ptk,j−1) )−1 ].
For each sibling w of A(pt , j), increase bw,t+1 with the following rate:

dbw,t+1
daS,t

=

1
2+ n−1
ψ(j) (uA(pt ,j−1),t

+

|TA(pt ,j−1) | −1
)
k

Thus, we design an online algorithm for the fractional k-sever problem as follows (see Algorithm
3.1).
1:
2:
3:
4:
5:
6:

At time t = 0, we set bp,1 = γp = 0 for all p and set bA(p,j),1 = 0 for any 1 ≤ j ≤ ℓ.
At time t ≥ 1, when a request pt arrives:
Initially, we set up,t = up,t−1 for all p, and bp,t+1 is initialized to bp,t .
If upt ,t = 0, then do nothing.
Otherwise, do the following:
P
xp,t = k = n − 1. So, S = [n].
Let S = {p : up,t < 1}. Since k = n − 1, |S| >
x∈S

While upt ,t 6= 0:
8:
Increasing aS,t with rate 1;
9:
For each 1 ≤ j ≤ ℓ, decrease every bA(pt ,j),t+1 with rate:
7:

dbA(pt ,j),t+1
daS,t

2+

1

|T

|

|T

|

n−1
= ψ(j)
[(uA(pt ,j),t + A(pk t ,j) )−1 − (uA(pt ,j−1),t + A(ptk,j−1) )−1 ],
For each sibling w of A(pt , j), increase bw,t+1 with the following rate:

10:
11:
12:

dbw,t+1
daS,t

13:

For any
1
σ

·

1
2+ n−1
|TA(pt ,j−1) | −1
)
k
ψ(j) (uA(pt ,j−1),t +
node v ′ in the path from w to a leaf

=

dbv′ ,t+1
dh

in Tw , if w′ be the child of v ′ ,

dbw′ ,t+1
dh

=

Algorithm 3.1: The online primal-dual algorithm for the fractional k-sever problem on a σ-HST.
Theorem 3.7. The online algorithm for the fractional k-sever problem on a σ-HST is of competitive
ratio 15 ln2 (1 + k).
7

In [32], Duru Türkoğlu study the relationship between fractional version and randomized version
of the k-sever problem, which is given as follows.
Lemma 3.8. The fractional k-sever problem is equivalent to the randomized k-sever problem on
the line or circle, or if k = 2 or k = n − 1 for arbitrary metric spaces.
Thus, we get the following conclusion:
Theorem 3.9. There is a randomized algorithm with competitive ratio 15 ln2 (1 + k) for the k-sever
problem on a σ-HST when n = k + 1.
By lemma 2.5, we get the following conclusion:
Theorem 3.10. There is an O(log2 k log n) competitive randomized algorithm for the k-sever problem on any metric space when n = k + 1 .

4

An O(ℓ log k)-competitive Fractional Algorithm for the k-Sever
Problem on a Weighted HST with Depth ℓ

In this section, we first give an O(ℓ log k)-competitive fractional algorithm for the k-Sever problem
on a weighted σ-HST with depth ℓ.
We give another some notations for a weighted HST. Let T̃ be a weighted σ-HST. For a node
D(v)
= d(p(v),v)
whose depth is j, let σj = D(w)
d(v,w) where w is a child of v. By the definition of a weighted σHST, σj ≥ σ for all 1 ≤ j ≤ ℓ−1. For a node v ∈ T̃ , if any leaf p ∈ L(T (v)) such that up,t = 1, we call
it a full node. By this definition, for a full node, uv,t = |L(Tv )|. Otherwise, we call it non-full node.
Let N F C(v) is the set of non-full children node of v, i.e., N F C(v) = {w|w ∈ C(v) and w is a non-full
node }. For a node v, let N L(Tv ) denote the set of non-full leaf nodes in T̃v . Let S = {p|up,t < 1}.
Let P ′ denotes the path from pt to root r: {A(pt , ℓ) = Pt , A(pt , ℓ−1), . . . , A(pt , 1), . . . , A(pt , 0) = r}.
For a node v ∈ P ′ , if there exists a p ∈ S\{pt } such that v is the first common ancestor of pt and p, we
call it a common ancestor node in P ′ . Let CA(pt , S) denote the set of common ancestor nodes in P ′ .
Suppose thatP
CA(pt , S) = {A(pt , ℓh ), . . . , A(pt , ℓ2 ), A(pP
t , ℓ1 )}, where ℓ1 < ℓ2 < . . . < ℓh . For a node
uw,t . Thus, for a full node v, uv,t = 0.
up,t . It is easy to know that uv,t =
v, let uv,t =
p∈S

w∈N F C(v)

For any ℓh < j < ℓ, uA(pt ,j),t = uA(pt ,ℓ),t . For any 0 ≤ j < ℓ1 , uA(pt ,0),t = uA(pt ,j),t = uA(pt ,ℓ1 ),t . For
any ℓi−1 < j < ℓi , uA(pt ,j),t = uA(pt ,ℓi ),t .
The primal-dual formulation for the fractional k-sever problem on a weighted HST is the same
as that on a HST in section 3. Based on the primal-dual formulation, the design idea of our online
algorithm is similar to the design idea in section 3. During the execution of our algorithm, it keeps
the following relation between the primal variable uv,t and dual variable bv,t+1 : uv,t = f (bv,t+1 ) =
bv,t+1
|N L(Tv )|
(exp( 2D(v)
ln(1 + k)) − 1). This relation determines how much mass of upt ,t should be
k
gradually moved out of leaf pt and how it should be distributed among other leaves S \ {pt } until
pt is completely fetched into the cache, i.e. upt ,t = 0. Thus,
P at any time t, the algorithm maintains
up,t = n − k.
a distribution (up1 ,t , . . . , upn ,t ) on the leaves such that
p∈[n]

In order to compute the the exact rate at which we should move mass upt ,t from pt through its
ancestor nodes at time t to other leaves S \ {pt } in the weighted σ-HST, using similar argument to
that in section 3, we get following several claims. Because of the space limit, we put their proofs
in the Appendix.
8

Lemma 4.1.

duv,t
dbv,t+1

Proof. Since uv,t =
claim.

=

ln(1+k)
2D(v) (uv,t

|N L(Tv )|
).
k

+

bv,t+1
|N L(Tv )|
(exp( 2D(v)
k

ln(1 + k)) − 1), we take the derivative over bv,t+1 and get the

Lemma 4.2. For a node v with ℓ(v) = j, if we increase variable bv,t+1 at rate h, then we have the
following equality:
P
dbw,t+1
db
|N L(Tv )|
w )|
1
) · v,t+1
=
· (uw,t + |N L(T
)
σj (uv,t +
k
dh
dh
k
w∈N F C(v)

Lemma 4.3. For v a node with ℓ(v) = j, assume that we increase (or decrease ) the variable bv,t+1
at rate h. If the increasing (or decreasing ) rate of each w ∈ N F C(v) is the same, then in order
to keep the Node Identity Property, we should set the increasing (or decreasing ) rate for each
child w ∈ N F C(v) as follows:
dbw,t+1
db
= σ1j · v,t+1
dh
dh
Repeatedly applying this lemma, we get the following corollary.
Corollary 4.4. For a node v with ℓ(v) = j and a path P from leaf pi ∈ Tv to v, if bv,t+1 is increased
( or decreased) at rate h and the increasing (decreasing) rate of all children of any v ′ ∈ P is the same,
P dbv′ ,t+1
db
= v,t+1
· φ(j), where φ(j) = (1 + σ1j + σj ·σ1j+1 + · · · + σj ·σj+11...σℓ−1 ) ≤ (1 + Θ( σ1 )).
then
dh
dh
v′ ∈P

Lemma 4.5. Let w1 , . . . , wm be the non-full children node of a node v (i.e., any wi ∈ N F C(v)).
Assume that we increase (or decrease) w1 at rate h and also increase w2 to wm at the same rate
db ′
db i ,t+1
. If we would like to maintain the amount uv,t unchanged, then
h. For i ≥ 2, let wdh,t+1 be wdh
we should have:
dbw′ ,t+1
dh

|NL(Tw1 )|
k
v )|
uv,t + |NL(T
k

uw1 ,t +

=

· (−

dbw1 ,t+1
dh

+

dbw′ ,t+1
)
dh

Theorem 4.6. When request pt arrives at time t, in order to keep the dual constraints tight and
node identity property, if aS,t is increased with rate 1, we should decrease every bA(pt ,j),t+1 for each
j ∈ {ℓ1 + 1, ℓ2 + 1, . . . , ℓh + 1} with rate:
dbA(pt ,j),t+1
daS,t

ur,t + |S|

|N L(T

|N L(T

)|

)|

A(pt ,j−1)
A(pt ,j)
= φ(j) k [(uA(pt ,j),t +
)−1 − (uA(pt ,j−1),t +
)−1 ].
k
k
For each sibling w ∈ N F C(v) of A(pt , j), increase bw,t+1 with the following rate:

dbw,t+1
daS,t

|S|

=

ur,t + k
φ(j)

(uA(pt ,j−1),t +

|N L(TA(pt ,j−1) )| −1
)
k

Thus, we design an online algorithm for the fractional k-sever problem on a weighted σ-HST as
follows (see Algorithm 4.1).
Theorem 4.7. The online algorithm for the fractional k-sever problem on a weighted σ-HST with
depth ℓ is of competitive ratio 4ℓ ln(1 + k).
By lemma 2.7, we get:
Theorem 4.8. There exists an O(log k log n)-competitive fractional algorithm for the k-sever problem on any σ-HST.
In [3], Nikhil Bansal et al. show the following conclusion.
9

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

At time t = 0, we set bp,1 = γp = 0 for all p.
At time t ≥ 1, when a request pt arrives:
Initially, we set up,t = up,t−1 for all p, and bp,t+1 is initialized to bp,t .
If upt ,t = 0, then do nothing.
Otherwise, do the following:
Let S = {p : up,t < 1}. Suppose that CA(pt , S) = {A(pt , ℓh ), . . . , A(pt , ℓ2 ), A(pt , ℓ1 )}, where
0 ≤ ℓ1 < ℓ2 < . . . < ℓh < ℓ.
While upt ,t 6= 0:
Increasing aS,t with rate 1;
For each j ∈ {ℓ1 + 1, ℓ2 + 1, . . . , ℓh + 1}, decrease every bA(pt ,j),t+1 with rate:
|S|
dbA(pt ,j),t+1
ur,t + k
=
daS,t
φ(j) [(uA(pt ,j),t
|N L(TA(pt ,j−1) )| −1
) ].
k

+

|N L(TA(pt ,j) )| −1
)
k

− (uA(pt ,j−1),t +

For each sibling w ∈ N F C(v) of A(pt , j), increase bw,t+1 with the following rate:
dbw,t+1
daS,t

ur,t + |S|

|N L(T

)|

A(pt ,j−1)
= φ(j)k (uA(pt ,j−1),t +
)−1
k
14:
For any node v ′ in the path from w to a leaf in N L(Tw ), if w′ ∈ N F C(v ′ ) and
db ′
db ′
ℓ(v ′ ) = j, wdh,t+1 = σ1j · vdh,t+1
15:
For p ∈ S \ {pt }), if some up,t reaches the value of 1, then we update S ← S \ {p} and
16:
the set N F C(v) for each ancestor node v of p.

13:

Algorithm 4.1: The online primal-dual algorithm for the fractional k-sever problem on a weighted
σ-HST.
Lemma 4.9. Let T be a σ-HST with σ > 5. Then any online fractional k-sever algorithm on T can
be converted into a randomized k-sever algorithm on T with an O(1) factor loss in the competitive
ratio.
Thus, we get the following conclusion by Theorem 4.8:
Theorem 4.10. Let T be a σ-HST with σ > 5. There is a randomized algorithm for the k-sever
problem with a competitive ratio of O(log k log n) on T .
By lemma 2.5, we get the following conclusion:
Theorem 4.11. For any metric space, there is a randomized algorithm for the k-sever problem
with a competitive ratio of O(log k log2 n).

5

Conclusion

In this paper, for any metric space with n points, we show that there exist a randomized algorithm
with O(log k log2 n)-competitive ratio for the k-sever problem, which improved the previous best
competitive ratio O(log2 k log3 n log log n).

Acknowledgments
We would like to thank the anonymous referees for their careful readings of the manuscripts and
many useful suggestions.
10

Wenbin Chen’s research has been partly supported by the National Natural Science Foundation
of China (NSFC) under Grant No.11271097., the research projects of Guangzhou education bureau
under Grant No. 2012A074. and the project KFKT2012B01 from State Key Laboratory for Novel
Software Technology, Nanjing University.

References
[1] Dimitris Achlioptas, Marek Chrobak, and John Noga. Competitive analysis of randomized
paging algorithms. Theoretical Computer Science, 234(1-2):203-218, 2000.
[2] Avrim Blum, Carl Burch, and Adam Kalai. Finely-competitive paging. Proceedings of the 40th
Annual Symposium on Foundations of Computer Science, page 450-456, 1999.
[3] Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph Naor. A PolylogarithmicCompetitive Algorithm for the k-Server Problem. FOCS 2011, pages 267-276.
[4] Nikhil Bansal, Niv Buchbinder, and Joseph (Seffi) Naor. A primal-dual randomized algorithm
for weighted paging. Proceedings of the 48th Annual IEEE Symposium on Foundations of
Computer Science, pages 507-517, 2007.
[5] N. Buchbinder, K. Jain, and J. Naor. Online primal-dual algorithms for maximizing ad-auctions
revenue. Proc. 14th European Symp. on Algorithms (ESA), pp. 253-264, 2007.
[6] N. Buchbinder and J. Naor. Online primal-dual algorithms for covering and packing problems.
Proc. 12th European Symp. on Algorithms (ESA), volume 3669 of Lecture Notes in Comput.
Sci., pages 689–701. Springer, 2005.
[7] N. Buchbinder and J. Naor. Improved bounds for online routing and packing via a primal-dual
approach. Proc. 47th Symp. Foundations of Computer Science, pages 293–304, 2006.
[8] Niv Buchbinder, Joseph Naor. The Design of Competitive Online Algorithms via a Primal-Dual
Approach. Foundations and Trends in Theoretical Computer Science 3(2-3): 93–263 (2009).
[9] Nikhil Bansal, Niv Buchbinder, and Joseph (Seffi) Naor. Towards the randomized k-server
conjecture: A primal-dual approach. Proceedings of the 21st Annual ACM- SIAM Symposium
on Discrete Algorithms, pp. 40-55, 2010.
[10] Nikhil Bansal, Niv Buchbinder, and Joseph (Seffi) Naor. Metrical task systems and the ksever problem on HSTs. In ICALP’10: Proceedings of the 37th International Colloquium on
Automata, Languages and Programming, 2010, pp.287-298.
[11] Yair Bartal. Probabilistic approximations of metric spaces and its algorithmic applications.
Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science, pages
184-193, 1996.
[12] Yair Bartal. On approximating arbitrary metrices by tree metrics. Proceedings of the 30th
Annual ACM Symposium on Theory of Computing, pages 161-168, 1998.

11

[13] Yair Bartal, Bela Bollobas, and Manor Mendel. A ramsy-type theorem for metric spaces and its
applications for metrical task systems and related problems. Proceedings of the 42nd Annual
IEEE Symposium on Foundations of Computer Science, pages 396-405, 2001.
[14] Yair Bartal and Eddie Grove. The harmonic k-server algorithm is competitive. Journal of the
ACM, 47(1):1-15, 2000.
[15] Yair Bartal, Nathan Linial, Manor Mendel, and Assaf Naor. On metric ramsey-type phenomena. Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pages
463C472, 2003.
[16] Yair Bartal, Elias Koutsoupias. On the competitive ratio of the work function algorithm for
the k-sever problem. Theoretical Computer Science, 324(2-3): 337-345.
[17] Avrim Blum, Howard J. Karloff, Yuval Rabani, and Michael E. Saks. A decomposition theorem
and bounds for randomized server problems. Proceedings of the 31st Annual IEEE Symposium
on Foundations of Computer Science, pages 197-207, 1992.
[18] Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. Cambridge
University Press, 1998.
[19] M. Chrobak and L. Larmore. An optimal on-line algorithm for k-servers on trees. SIAM Journal
on Computing, 20(1): 144-148, 1991.
[20] A. Coté, A. Meyerson, and L. Poplawski. Randomized k-server on hierarchical binary trees.
Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 227-234,
2008.
[21] B. Csaba and S. Lodha. A randomized on-line algorithm for the k-server problem on a line.
Random Structures and Algorithms, 29(1): 82-104, 2006.
[22] Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics. Proceedings of the 35th Annual ACM Symposium on Theory of
Computing, pages 448-455, 2003.
[23] A. Fiat, Y. Rabani, and Y. Ravid. Competitive k-server algorithms. Journal of Computer and
System Sciences, 48(3): 410-428, 1994.
[24] Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Dominic Sleator, and
Neal E. Young. Competitive paging algorithms. Journal of Algorithms, 12(4): 685-699, 1991.
[25] Edward F. Grove. The harmonic online k-server algorithm is competitive. Proceedings of the
23rd Annual ACM Symposium on Theory of Computing, pages 260-266, 1991.
[26] Elias Koutsoupias. The k-sever problem. Computer Science Review. Vol. 3. No. 2. Pages 105118, 2009.
[27] Elias Koutsoupias and Christos H. Papadimitriou. On the k-server conjecture. Journal of the
ACM, 42(5): 971-983, 1995.

12

[28] M.S. Manasse, L.A. McGeoch, and D.D. Sleator. Competitive algorithms for online problems.
Proceedings of the 20th Annual ACM Symposium on Theory of Computing, pages 322-333,
1988.
[29] M. Manasse, L.A. McGeoch, and D. Sleator. Competitive algorithms for server problems.
Journal of Algorithms, 11: 208-230, 1990.
[30] Lyle A. McGeoch and Daniel D. Sleator. A strongly competitive randomized paging algorithm.
Algorithmica, 6(6): 816-825, 1991.
[31] Daniel D. Sleator and Robert E. Tarjan. Amortized efficiency of list update and paging rules.
Communications of the ACM, 28(2): 202-208, 1985.
[32] Duru Türkoğlu. The k-sever problem and fractional analysis. Master’s Thesis, The University
of Chicago, 2005. http://people.cs.uchicago.edu/∼duru/papers/masters.pdf.

Appendix
Proofs for claims in section 3
The proof for Lemma 3.2 is as follows:
P

Proof. Since it is required to maintain uv,t =

uw,t, we take the derivative of both sides and

w∈C(v)

get that:

duv,t
dbv,t+1

·

dbv,t+1
dh

P

=

w∈C(v)

By lemma 3.1, we get:

duw,t
dbw,t+1

·

dbw,t+1
dh .

ln(1+k)
2D(v) (uv,t

+

D(v)
Since D(w)
= σ, we get :
P dbw,t+1
dbv,t+1
|Tv |
1
=
σ (uv,t + k ) ·
dh
dh
w∈C(v)

|Tv |
k )

P

=

w∈C(v)

· (uw,t +

dbw,t+1
dh

·

ln(1+k)
2D(w) (uw,t

+

|Tv |
k ).

|Tw |
k )

The proof for Lemma 3.3 is as follows:
Proof. By above Lemma 3.2, if the increasing (or decreasing ) rate of each w ∈ C(v) is the same,
we get that:
P
dbv,t+1
db
db
|Tv |
1
= w,t+1
·
· (uv,t + |Tkv | ).
(uw,t + |Tkw | ) = w,t+1
σ (uv,t + k ) ·
dh
dh
dh
So, we get that:

dbw,t+1
dh

=

1
σ

·

w∈C(v)
dbv,t+1
dh

The proof for Lemma 3.5 is as follows:
Proof. By lemma 3.2, in order to keep the amount uv,t unchanged, we get:
P
dbw1 ,t+1
dbw,t+1
1 )|
· (uw1 ,t + |T (w
)+
· (uw,t + |T (w)|
dh
k
dh
k ) = 0.
Thus,

db 1 ,t+1
( wdh

db

−
db

dbw′ ,t+1
)
dh
′

w∈C(v)\{w1 }
1 )|
· (uw1 ,t + |T (w
)
k

1 ,t+1
So, ( wdh
− wdh,t+1 ) · (uw1 ,t +
Hence, we get the claim.

|T (w1 )|
)
k

+

+

dbw′ ,t+1
dh

dbw′ ,t+1
dh

13

·

·

P

(uw,t +

w∈C(v)
(uv,t + |T (v)|
k )

|T (w)|
k )

=0

=0

The proof for Theorem 3.6 is as follows:
Proof. When request pt arrives at time t, we move mass upt ,t from pt through its ancestor nodes
to other leaves [n] \ {pt }, i.e. upt ,t is decreased and up,t is increased for any p ∈ [n] \ {pt }. Since
these mass moves out of each subtree TA(pt ,j) for each 1 ≤ j ≤ ℓ, uA(pt ,j),t is decreased. By
b

t ,j),t+1
uA(pt ,j),t = f (bA(pt ,j),t+1 ) = |Tkv | (exp( A(p
ln(1 + k)) − 1) (we need to keep this relation during
2D(v)
the algorithm), bA(pt ,j),t+1 also decreases for each 1 ≤ j ≤ ℓ. On the other hand, up,t is increased
for each p ∈ [n] \ {pt }. Thus, for each node v whose Tv doesn’t contain pt , its mass uv,t is also
increased. For each node v whose Tv doesn’t contain pt , it must be a sibling of some node A(pt , j).
For each 1 ≤ j ≤ ℓ, we assume that all siblings v ′ of node A(pt , j) increase bv′ ,t+1 at the same rate.
In the following, we will compute the increasing (or decreasing) rate of all dual variables in the
b
t ,j),t+1
be the decreasing rate of bA(pt ,j),t+1
σ-HST regarding aS . For 1 ≤ j ≤ ℓ, let ∇bj = − A(pda
S

b

regarding aS . For 1 ≤ j ≤ ℓ, let ∇b′j = w,t+1
daS be the increasing rate of bw,t+1 for any siblings w of
A(pt , j) regarding aS .
Using from top to down method, we can get a set of equations about the quantities ∇bj and
∇b′j . First, we consider the siblings of A(pt , 1) ( i.e. those nodes are children of root r, but they
are not A(pt , 1)). Let w be one of these siblings. If bw,t+1 is raised by ∇b′1 , by Corollary 3.4, the
sum of ∇b′ on any path from a leaf in Tw to w must be ψ(1) · ∇b′1 . Since aS is increasing with rate
1, it forces ψ(1) · ∇b′1 = 1 in order to maintain the dual constraint (3) tight for leaves in Tw .
This considers the dual constraints for these leaves. Now, this increasing mass must be canceled
out by decreasing the mass in TA(pt ,1) since the mass ur,t in Tr is not changed. Thus, in order to
maintain the “Node Identity Property” of root, by Lemma 3.5, we must set ∇b1 such that:
∇b′1 = (∇b1 + ∇b′1 ) ·

|T(A(p ,1)) |
t
)
k

(uA(pt ,1),t +
n
1+ n−1

For siblings of node A(pt , 2), we use the similar argument. Let w be a sibling of A(pt , 2).
Consider a path from a leaf in Tw to the w. Their dual constraint (3) already grows at rate
1 + ψ(1)∇b1 . This must be canceled out by increasing bw,t+1 , and if bw,t+1 is raised by ∇b′2 , by
corollary 3.4, the sum of ∇b′ on any path from a leaf in Tw to w must be ψ(2) · ∇b′2 . Thus, ∇b′2
must be set such that: ψ(2) · ∇b′2 = 1 + ψ(1) · ∇b1
Again, this increasing mass must be canceled out by decreasing the mass in TA(pt ,2) . In order
to keep the “Node Identity Property” of A(pt , 1), by Lemma 3.5. we must set ∇b2 such that:
∇b′2 = (∇b2 + ∇b′2 ) ·

|TA(p ,2) |
t
)
k
|T(A(p ,1) |
t
(uA(pt ,1),t +
)
k

(uA(pt ,2),t +

Continuing this method, we obtain a system of linear equations about all ∇bj and ∇b′j (1 ≤
j ≤ ℓ). For maintaining the dual constraints tight, we get the following equations:
ψ(1) · ∇b′1 = 1
ψ(2) · ∇b′2 = 1 + ψ(1) · ∇b1
..
.
ℓ−1
P
ψ(ℓ) · ∇b′ℓ = 1 +
ψ(i)∇bi
i=1

For keeping the node identity property, we get the following equations:
∇b′1 = (∇b1 + ∇b′1 ) ·

|T(A(p ,1)) |
t
)
k

(uA(pt ,1),t +
n
1+ n−1

14

∇b′2 = (∇b2 + ∇b′2 ) ·
..
.
∇b′ℓ

= (∇bℓ +

∇b′ℓ )

·

|T(A(p ,2)) |
t
)
k
|T(A(p ,1)) |
t
(uA(pt ,1),t +
)
k

(uA(pt ,2),t +

|T(A(p ,ℓ)) |
t
)
k
|T(A(p ,ℓ−1)) |
t
)
(uA(pt ,ℓ−1),t +
k

(uA(pt ,ℓ),t +

.

We continue to solve the system of linear equations.
For each 1 ≤ j ≤ ℓ,
j−1
P
ψ(j) · ∇b′j = 1 +
ψ(i)∇bi
=1+

j−2
P

i=1

ψ(i)∇bi + ψ(j − 1)∇bj−1

i=1

= ψ(j − 1) · ∇b′j−1 + ψ(j − 1)∇bj−1
= ψ(j − 1) · (∇b′j−1 + ∇bj−1 ).
|T(A(p ,j−1)) |
t
)
k
|T(A(p ,j−2)) |
t
(uA(pt ,j−2),t +
)
k
|T(A(p ,j−2)) |
t
)
(uA(pt ,j−2),t +
k
|T(A(p ,j−1)) |
t
(uA(pt ,j−1),t +
)
k

Since ∇b′j−1 = (∇bj−1 + ∇b′j−1 ) ·
ψ(j)∇b′j = ψ(j − 1)∇b′j−1 ·

(uA(pt ,j−1),t +

, we get:

Solving the recursion, we get:
n
1+ n−1
∇b′j =
|T(A(p ,j−1)) |
∇bj =

ψ(j)·(uA(pt ,j−1),t +
n
1+ n−1
ψ(j) · [(uA(pt ,j),t

t
k

+

)
|T(A(pt ,j)) | −1
)
k

− (uA(pt ,j−1),t +

|T(A(pt ,j−1)) | −1
) ]
k

The proof for Theorem 3.7 is as follows:
Proof. Let P denote the value of the objective function of the primal solution and D denote the
value of the objective function of the dual solution. Initially, let P = 0 and D = 0. In the following,
we prove three claims:
(1) The primal solution produced by the algorithm is feasible.
(2) The dual solution produced by the algorithm is feasible.
(3) P ≤ 15 ln2 (1 + k)D.
By three claims and weak duality of linear programs, the theorem follows immediately.
First,
we prove the claim (1) as follows. At any time t, since S = [n] and the algorithm keeps
P
= n − k = 1 = |S| − k. So, the primal constraints (3.1) are satisfied.
p∈[n]

Second, we prove the claim (2) as follows. By theorem 3.6, the dual constraints (3.6) are
satisfied. Obviously, dual constraints (3.7) are satisfied. For any node v, if bv,t+1 = 0, then
uv,t = 0; if bv,t+1 = 2D(v), then uv,t = |Tv |. Thus, the dual constraints (3.8) are satisfied.
Third, we prove claim (3) as follows. If the algorithm increases the variables aS,t at some time
∂D
= |S| − k = n − (n − 1) = 1. Let’s compute the primal cost. At depth j(1 ≤ j ≤ ℓ),
t, then: ∂a
S,t
we compute the movement cost of our algorithm by the change of ∇b′j as follows.
P
db′
du
2D(w) · dbw,t
· aSj
′
j
w∈C(A(pt ,j−1))\{A(pt ,j)}
P
= ∇b′j ·
2D(w)
w∈C(A(pt ,j−1))\{A(pt ,j)}

·

ln(1+k)
2D(w) (uw,t

15

+

|Tw |
k )

=

1
2+ n−1
ψ(j)

≤

5
2

P

(uw,t +
w∈C(A(pt ,j−1))\{A(pt ,j)}
|TA(p ,j−1) |
t
uA(p ,j−1),t +
k
P t
|T |
(uw,t + kw )
w∈C(A(pt ,j−1))\{A(pt ,j)}
|TA(p ,j−1) |
t
uA(pt ,j−1),t +
k

|Tw |
)
k

· ln(1 + k) ·

· ln(1 + k) ·

Let Bj denote uA(pt ,j),t +

|TA(pt ,j) |
.
k

P

Then

(uw,t +

w∈C(A(pt ,j−1))\{A(pt ,j)}

|Tw |
k )

= Bj−1 − Bj .

Hence, the total
cost over all ℓ levels is
Pℓ movement
Bj−1 −Bj
5
ln(1
+
k)
·
j=1 Bj−1
2
P
Bj
5
= 2 ln(1 + k) · ℓj=1 (1 − Bj−1
)
P
B
ℓ
j
≤ 52 ln(1 + k) · j=1 ln Bj−1
=
=

5
2
5
2
5
2
5
2
5
2

0
ln(1 + k) · ln B
Bℓ
ln(1 + k) · ln u B0+ 1
pt ,t

k

≤ ln(1 + k) · ln kB0
≤ ln(1 + k) · 2 ln k · B0
1
≤ ln(1 + k) · 2 ln k · (2 + n−1
)
2
= 15 ln (1 + k)
where the first inequality holds since 1 ≤ y − ln y for any 0 ≤ y ≤ 1.
Thus, we get P ≤ 15 ln2 (1 + k)D.
Let OP T be the cost of the best offline algorithm. Pmin be the optimal primal solution and
Dmax be the optimal dual solution. Then, Pmin ≤ OP T since OP T is a feasible solution for the
15 ln2 (1+k)D
P
P
≤
primal program. Based on the weak duality, Dmax ≤ Pmin . Hence, OP
T ≤ Pmin ≤
Pmin
15 ln2 (1+k)Dmax
Pmin

2

min
≤ 15 ln (1+k)P
= 15 ln2 (1 + k).
Pmin
So, the competitive ratio of this algorithm is 15 ln2 (1 + k).

Proofs for claims in section 4
The proof for Lemma 4.2 is as follows:
P

Proof. Since it is required to maintain uv,t =

uw,t, we take the derivative of both sides

w∈N F C(v)

and get that:
dbv,t+1
duv,t
=
dbv,t+1 ·
dh

P

duw,t
dbw,t+1

·

w∈N F C(v)
ln(1+k)
2D(v) (uv,t

By lemma 3.1, we get:

D(v)
Since D(w)
= σj , we get :
db
|N L(Tv )|
1
) · v,t+1
σj (uv,t +
k
dh

=

dbw,t+1
dh .

+

|N L(Tv )|
)
k

P
w∈N F C(v)

dbw,t+1
dh

=

P
w∈N F C(v)

· (uw,t +

dbw,t+1
dh

·

ln(1+k)
2D(w) (uw,t

+

|N L(Tw )|
).
k

|N L(Tw )|
)
k

The proof for Lemma 4.3 is as follows:
Proof. By Lemma 4.2, if the increasing (or decreasing ) rate of each w ∈ N F C(v) is the same, we
get that:

16

1
σj (uv,t

+

db
|N L(Tv )|
) · v,t+1
k
dh

So, we get that:

dbw,t+1
dh

=

=
1
σj

dbw,t+1
dh

·

P

·

(uw,t +

w∈N F C(v)

|N L(Tw )|
)
k

=

dbw,t+1
dh

· (uv,t +

|N L(Tv )|
).
k

dbv,t+1
dh

The proof for Lemma 4.5 is as follows:
Proof. By lemma 4.2, in order to keep the amount uv,t unchanged, we get:
P
dbw1 ,t+1
|N L(Tw1 )|
dbw,t+1
w )|
· (uw1 ,t +
)+
· (uw,t + |N L(T
) = 0.
dh
k
dh
k
Thus,

db 1 ,t+1
( wdh

db

−
db

dbw′ ,t+1
)
dh

w∈N F C(v)\{w1 }
|N L(Tw1 )|
· (uw1 ,t +
)
k

′

1 ,t+1
− wdh,t+1 ) · (uw1 ,t +
So, ( wdh
Hence, we get the claim.

|N L(Tw1 )|
)
k

+

+

dbw′ ,t+1
dh

dbw′ ,t+1
dh

·

·

P

(uw,t +

w∈N F C(v)
v )|
(uv,t + |N L(T
)
k

|N L(Tw )|
)
k

=0

=0

The proof for Theorem 4.6 is as follows:
Proof. When request pt arrives at time t, we move mass upt ,t from pt through its ancestor nodes to
other non-full leaves nodes S \ {pt }, i.e. upt ,t is decreased and up,t is increased for any p ∈ S \ {pt }.
Since these mass moves out of each subtree TA(pt ,j) for each 1 ≤ j ≤ ℓ, uA(pt ,j),t is decreased. By
b

v )|
t ,j),t+1
(exp( A(p
uA(pt ,j),t = f (bA(pt ,j),t+1 ) = |N L(T
ln(1 + k)) − 1) (we need to keep this relation
k
2D(v)
during the algorithm), bA(pt ,j),t+1 also decreases for each 1 ≤ j ≤ ℓ. On the other hand, up,t is
increased for each p ∈ S \ {pt }. Thus, for each non-full node v whose Tv doesn’t contain pt , its mass
uv,t is also increased. For each non-full node v whose Tv doesn’t contain pt , it must be a sibling of
some node A(pt , j) where j ∈ {ℓ1 , . . . , ℓh }. We assume that all siblings v ′ of any node v increase
bv′ ,t+1 at the same rate
In the following, we will compute the increasing (or decreasing) rate of all dual variables in
b
t ,j),t+1
be the decreasing rate of
the weighted σ-HST regarding aS . For 1 ≤ j ≤ ℓ, let ∇bj = − A(pda
S

b

bA(pt ,j),t+1 regarding aS . For each j ∈ {ℓ1 + 1, ℓ2 + 1, . . . , ℓh + 1}, let ∇b′j = w,t+1
daS be the increasing
rate of bw,t+1 for any siblings w ∈ N F C(A(pt , j)) of A(pt , j) regarding aS .
Using from top to down method, we can get a set of equations about the quantities ∇bj and
∇b′j . First, we consider the siblings of A(pt , ℓ1 + 1) ( i.e. those nodes are children of A(pt , ℓ1 ),
but they are not A(pt , ℓ1 + 1)). Let w be one of these siblings. If bw,t+1 is raised by ∇b′ℓ1 +1 , by
Corollary 4.4, the sum of ∇b′ on any path from a leaf in Tw to w must be φ(ℓ1 + 1) · ∇b′ℓ1 +1 . Since
aS is increasing with rate 1, it forces φ(ℓ1 + 1) · ∇b′ℓ1 +1 = 1 in order to maintain the dual constraint
(3) tight for non-full leaf nodes in Tw .
This considers the dual constraints for these non-full leaf nodes. Now, this increasing mass
must be canceled out by decreasing the mass in TA(pt ,ℓ1 +1) since the mass uA(pt ,ℓ1 ),t in TA(pt ,ℓ1 ) is
not changed. Thus, in order to maintain the “Node Identity Property” of A(pt , ℓ1 ), by Lemma 4.5,
we must set ∇b1 such that:
∇b′ℓ1 +1

= (∇bℓ1 +1 +

|NL(T(A(p ,ℓ +1)) )|
t 1
)
k
|S|
uA(pt ,ℓ1 ),t + k
|NL(T(A(p ,ℓ )) )|
t 2
(uA(pt ,ℓ2 ),t +
)
k
|S|
ur + k

∇b′ℓ1 +1 )

= (∇bℓ1 +1 + ∇b′ℓ1 +1 ) ·

·

(uA(pt ,ℓ1 +1),t +

For siblings of node A(pt , ℓ2 +1), we use the similar argument. Let w be a sibling of A(pt , ℓ2 +1).
Consider a path from a non-full leaf node in Tw to the w. Their dual constraint (3.6) already grows
17

at rate 1 + φ(ℓ1 + 1)∇bℓ1 +1 . This must be canceled out by increasing bw,t+1 , and if bw,t+1 is raised
by ∇b′ℓ2 +1 , by corollary 4.4, the sum of ∇b′ on any path from a leaf in Tw to w must be φ(2) · ∇b′2 .
Thus, ∇b′2 must be set such that: φ(ℓ2 + 1) · ∇b′ℓ2 +1 = 1 + φ(ℓ1 + 1) · ∇bℓ1 +1 .
Again, this increasing mass must be canceled out by decreasing the mass in TA(pt ,ℓ2 ) . In order
to keep the “Node Identity Property” of A(pt , ℓ2 ), by Lemma 4.5. we must set ∇bℓ2 +1 such that:
|NL(TA(p ,ℓ +1) )|
t 2
)
k
|NL(T(A(p ,ℓ ) )|
t
2
(uA(pt ,ℓ2 ),t +
)
k
|NL(TA(p ,ℓ ) )|
t
3
(uA(pt ,ℓ3 ),t +
)
k
|NL(T(A(p ,ℓ ) )|
t
2
(uA(pt ,ℓ2 ),t +
)
k

∇b′ℓ2 +1 = (∇bℓ2 +1 + ∇b′ℓ2 +1 ) ·
= (∇bℓ2 +1 + ∇b′ℓ2 +1 ) ·

(uA(pt ,ℓ2 +1),t +

Continuing this method, we obtain a system of linear equations about all ∇bj and ∇b′j (j ∈
{ℓ1 +1, ℓ2 +1, . . . , ℓh +1}). For maintaining the dual constraints tight, we get the following equations:
φ(ℓ1 + 1) · ∇b′ℓ1 +1 = 1
φ(ℓ2 + 1) · ∇b′ℓ2 +1 = 1 + φ(ℓ1 + 1) · ∇bℓ1 +1
..
.
h−1
P
ψ(ℓh + 1) · ∇b′ℓh +1 = 1 +
φ(ℓi + 1)∇bℓi +1
i=1

For keeping the node identity property, we get the following equations:
∇b′ℓ1 +1

= (∇bℓ1 +1 +

∇b′ℓ1 +1 )

·

∇b′ℓ2 +1 = (∇bℓ2 +1 + ∇b′ℓ2 +1 ) ·
..
.
∇b′ℓh +1

= (∇bℓh +1 +

∇b′ℓh +1 )

·

|NL(T(A(p ,1)) )|
t
)
k
|S|
ur + k
|NL(T(A(p ,ℓ )) )|
t 3
)
(uA(pt ,ℓ3 ),t +
k
|NL(T(A(p ,ℓ )) )|
t
2
(uA(pt ,ℓ2 ),t +
)
k

(uA(pt ,ℓ2 ),t +

|NL(T(A(p ,ℓ)) )|
t
)
k
|NL(T(A(p ,ℓ )) )|
t h
(uA(pt ,ℓh ),t +
)
k

(uA(pt ,ℓ),t +

.

We continue to solve the system of linear equations.
For each 1 ≤ j ≤ h,
j−1
P
φ(ℓj + 1) · ∇b′ℓj +1 = 1 +
φ(ℓi + 1)∇bℓi +1
=1+

j−2
P
i=1

i=1

φ(ℓi + 1)∇bℓi +1 + φ(ℓj−1 + 1)∇bℓj−1 +1

= φ(ℓj−1 + 1) · ∇b′ℓj−1 +1 + φ(j − 1)∇bℓj−1 +1
= φ(ℓj−1 + 1) · (∇b′ℓj−1 +1 + ∇bℓj−1 +1 ).
Since

∇b′ℓj−1 +1

= (∇bℓj−1 +1 +

∇b′ℓj−1 +1 ) ·

ψ(ℓj + 1)∇b′ℓj +1 = ψ(ℓj−1 + 1)∇b′ℓj−1 +1 ·

|NL(T(A(p ,ℓ )) )|
t j
)
k
|NL(T(A(p ,ℓ
)|
t j−1 ))
(uA(pt ,ℓj−1 ),t +
)
k
|NL(T(A(p ,ℓ
)|
))
t j−1
)
(uA(pt ,ℓj−1 ),t +
k
|NL(T(A(p ,ℓ )) )|
t j
(uA(pt ,ℓj ),t +
)
k

(uA(pt ,ℓj ),t +

, we get:

Solving the recursion, we get:
∇b′ℓj +1 =

ur + |S|
k
φ(ℓj +1)·(uA(pt ,ℓj ),t +

|NL(T(A(p ,ℓ )) )|
t j
)
k

|S|

∇bℓj +1 =
=

|N L(T(A(pt ,ℓj )) )|
|N L(T(A(pt ,ℓj+1 )) )|
)−1 − (uA(pt ,ℓj ),t +
)−1 ]
k
k
|S|
|N L(T(A(pt ,ℓj +1)) )|
|N L(T(A(pt ,ℓj )) )|
ur + k
)−1 − (uA(pt ,ℓj ),t +
)−1 ]
k
k
φ(ℓj +1) · [(uA(pt ,ℓj +1),t +

ur + k
φ(ℓj +1)

· [(uA(pt ,ℓj+1 ),t +

18

The proof for Theorem 4.7 is as follows:
Proof. Let P denote the value of the objective function of the primal solution and D denote the
value of the objective function of the dual solution. Initially, let P = 0 and D = 0. In the following,
we prove three claims:
(1) The primal solution produced by the algorithm is feasible.
(2) The dual solution produced by the algorithm is feasible.
(3) P ≤ 2 ln(1 + k)D.
By three claims and weak duality of linear programs, the theorem follows immediately.
The proof of claim (1) and (2) are similar to that of claim (1) and (2) in section 3.7.
Third, we prove claim (3) as follows. If the algorithm increases the variables aS,t at some time
∂D
= |S| − k. Let’s compute the primal cost. At depth j ∈ {ℓ1 + 1, ℓ2 + 1, . . . , ℓh + 1},
t, then: ∂a
S,t
we compute the movement cost of our algorithm by the change of ∇b′j as follows.
P
db′
du
2D(w) · dbw,t
· aSj
′
j

w∈N F C(A(pt ,j−1))\{A(pt ,j)}
= ∇b′j

P

2D(w) ·

w∈C(A(pt ,j−1))\{A(pt ,j)}

=

|S|
ur,t + k

φ(j)
P

=

p∈S

=

up,t + |S|
k
φ(j)
P

+

|N L(Tw )|
)
k

P

w )|
)
(uw,t + |NL(T
k
w∈C(A(pt ,j−1))\{A(pt ,j)}
|NL(TA(p ,j−1) )|
t
uA(pt ,j−1),t +
k
P
w )|
(uw,t + |NL(T
)
k
w∈C(A(pt ,j−1))\{A(pt ,j)}
|NL(TA(p ,j−1) )|
t
uA(pt ,j−1),t +
k

· ln(1 + k) ·

P

w )|
)
(uw,t + |NL(T
k
w∈C(A(pt ,j−1))\{A(pt ,j)}
|NL(TA(p ,j−1) )|
φ(j)
t
uA(pt ,j−1),t +
k
P
P
|S|−1
w )|
(uw,t + |NL(T
(
up,t + k +2(|S|−k))
)
k
w∈C(A(pt ,j−1))\{A(pt ,j)}
p∈S\{pt }
|NL(TA(p ,j−1) )|
φ(j)
t
uA(pt ,j−1),t +
k
P
|T (w)|
(uw,t + k )
w∈C(A(pt ,j−1))\{A(pt ,j)}
(|S|−1)
|NL(TA(p ,j−1) )|
k
t
uA(pt ,j−1),t +
k
P
w )|
)
(uw,t + |NL(T
k
w∈C(A(pt ,j−1))\{A(pt ,j)}
|NL(TA(p ,j−1) )|
t
uA(pt ,j−1),t +
k

(

<

· ln(1 + k) ·

ln(1+k)
2D(w) (uw,t

p∈S\{pt }

+2)
up,t + |S|−1
k

· ln(1 + k) ·

· ln(1 + k) ·

≤ (3(|S| − k) +

) · ln(1 + k) ·

≤ 4 · ln(1 + k) · (|S| − k) ·

≤ 4 · ln(1 + k) · (|S| − k), since

P

(uw,t +

w∈C(A(pt ,j−1))\{A(pt ,j)}
|N L(T

)|

A(pt ,j−1)
.
uA(pt ,j−1),t +
k
Where the first inequality holds since

|N L(Tw )|
)
k

≤

P

up,t < |S| − k, the reason is that the constraint
P
up,t =
at time t is not satisfied otherwise the algorithm stop increasing the variable up,t (Since
p∈S
P
up,t < |S| − k ⇔ upt ,t = 0, i.e the algorithm stop increasing the variables). In
|S| − k,
p∈S\{pt }

p∈S\{pt }

addition, when |S| ≥ k + 1, |S|−1
= |S| − k.
k
Thus, the total cost of all j depth is at most 4ℓ · ln(1 + k) · (|S| − k). Hence, we get P ≤
4ℓ̇ · ln(1 + k) · D.
19

So, the competitive ratio of this algorithm is 4ℓ ln(1 + k).

20

