Algorithms for k-server problems

Citation for published version (APA):

Koumoutsos, G. (2018). Algorithms for k-server problems. [Phd Thesis 1 (Research TU/e / Graduation TU/e),
Mathematics and Computer Science]. Technische Universiteit Eindhoven.

Document status and date:

Published: 06/09/2018

Document Version:
Publisher’s PDF, also known as Version of Record (includes final page, issue and volume numbers)

Please check the document version of this publication:

• A submitted manuscript is the version of the article upon submission and before peer-review. There can be
important differences between the submitted version and the official published version of record. People
interested in the research are advised to contact the author for the final version of the publication, or visit the
DOI to the publisher's website.
• The final author version and the galley proof are versions of the publication after peer review.
• The final published version features the final layout of the paper including the volume, issue and page
numbers.
Link to publication

General rights
Copyright and moral rights for the publications made accessible in the public portal are retained by the authors and/or other copyright owners
and it is a condition of accessing publications that users recognise and abide by the legal requirements associated with these rights.

• Users may download and print one copy of any publication from the public portal for the purpose of private study or research.
• You may not further distribute the material or use it for any profit-making activity or commercial gain
• You may freely distribute the URL identifying the publication in the public portal.

If the publication is distributed under the terms of Article 25fa of the Dutch Copyright Act, indicated by the “Taverne” license above, please
follow below link for the End User Agreement:
[Link]/taverne

Take down policy

If you believe that this document breaches copyright please contact us at:
openaccess@[Link]
providing details and we will investigate your claim.

Download date: 30. Apr. 2023

Algorithms for k-Server Problems

Grigorios Koumoutsos
This research was supported by the European Research Council (ERC) grant
617951 (“Algorithms for coping with uncertainty and intractability”).

A catalogue record is available from the Eindhoven University of Technology

Library.
ISBN: 978-94-9301-405-3
Printed by Gildeprint, Enschede.
Algorithms for k-Server Problems

PROEFSCHRIFT

ter verkrijging van de graad van doctor aan de Technische Universiteit

Eindhoven, op gezag van de rector magnificus [Link]. F.P.T. Baaijens,
voor een commissie aangewezen door het College voor Promoties, in het
openbaar te verdedigen op donderdag 6 september 2018 om 16:00 uur

door

Grigorios Koumoutsos

geboren te Amarousion, Griekenland

Dit proefschrift is goedgekeurd door de promotoren en de samenstelling van de
promotiecommissie is als volgt:
Voorzitter: prof. dr. ir. B. Koren
Promotor: prof. dr. N. Bansal
Copromotoren: dr. J. Nederlof
dr. A. Rosén (CNRS and University Paris Diderot)
Leden: prof. dr. E. Koutsoupias (University of Oxford)
prof. dr. J. Naor (Technion)
prof. dr. F.C.R. Spieksma
prof. dr. M.T. de Berg
prof. dr. L. Stougie (Vrije Universiteit Amsterdam)

Het onderzoek dat in dit proefschrift wordt beschreven is uitgevoerd in over-

eenstemming met de TU/e Gedragscode Wetenschapsbeoefening.
Acknowledgments

I would like to express my deep gratitude to my advisor Nikhil Bansal for

his guidance and support. His passion about research was a great source of
motivation and it was a pleasure to work with him. I would also like to thank
him for teaching me how to think in a simple way and how to present my
work to a broad audience. Thanks also for the financial support for attending
many conferences, workshops and summer schools around the world. I could
not have asked for better conditions for pursuing a PhD.
I would like to thank the members of my thesis committee. Jesper Nederlof,
Leen Stougie, Seffi Naor, Frits Spieksma and Mark de Berg, thank you all for
reviewing my thesis and for being part of my graduation. Special thanks to
Elias Koutsoupias, my undergraduate supervisor, for being a member of the
committee and for his inspiring lectures back in fall 2010 at the University of
Athens, which served as a springboard for my journey in the area of algorithms.
I am grateful to Adi Rosén for his supervision, support and advice since 2013,
and for his hospitality and financial support for my research visits in Paris.
I would like to thank Marek Eliáš for being a colleague, a collaborator, a
coauthor, a roommate in many trips and a friend. I would also like to thank
all my coauthors. Lukasz Jeż, Kirk Pruhs, Jesper Nederlof, Seeun William
Umboh and Martin Böhm, I really enjoyed working with you all. Thanks to
László Kozma, Janardhan Kulkarni, Spyros Angelopoulos, Marc Renault and
René Sitters for many stimulating research discussions.
Thanks to Bouke Cloostermans, Tjark Vredeveld and Shashwat Garg for
the nice environment at the office. Thanks to Jorn van der Pol and Aleksandar
Markovic for organizing great dinners in Eindhoven.
During the PhD studies it was sometimes hard to keep a balance between
work and personal life. I would like to thank my friends for the nice moments I
had with them. Jerry, Stelios, Christos, Tilemachos, Danae and Kyveli, thank
you for discovering Maastricht together. Special thanks to all my friends from
Greece for their presence and support at all times and for the great trips during
those years. I am not mentioning your names, you know who you are!
I am grateful to my parents for their unconditional support and love.
Thanks to my father for making me love Mathematics and Computer Science

v
since childhood. Thanks to my mother for all her patience and understanding.
Thanks to my brother for his presence and love at all times.
Last and most importantly, I would like to thank Mina for standing by me
during the PhD life. Mina, in the last 8 years you have been a girlfriend, a
partner, the best friend, a flatmate, a travel buddy and a “FightFun” classmate.
Thank you for your unlimited support throughout the highs and lows of those
years. Thank you for sharing your life with me. I look forward to everything
that is to come.

vi
Contents

1 Introduction 1
1.1 Online Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 Competitive Analysis . . . . . . . . . . . . . . . . . . . 2
1.1.2 Metrical Task Systems . . . . . . . . . . . . . . . . . . . 4
1.1.3 The k-Server Problem . . . . . . . . . . . . . . . . . . . 5
1.2 The (h, k)-Server Problem . . . . . . . . . . . . . . . . . . . . . 7
1.3 The Generalized k-Server Problem . . . . . . . . . . . . . . . . 8

2 Tight Bounds for Double Coverage Against Weak Adversaries 11

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.3 Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Extension to Trees . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Competitive Ratio of DC for the Paging Problem . . . . . . . . 26

3 The (h, k)-Server Problem on Bounded Depth Trees 29

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 Lower Bound for Double Coverage on Depth-2 HSTs . . . . . . 31
3.3 Algorithm for Depth-d Trees . . . . . . . . . . . . . . . . . . . 33
3.3.1 Algorithm Description . . . . . . . . . . . . . . . . . . . 34
3.3.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.4 Algorithm for Bounded-Diameter Trees . . . . . . . . . . . . . 42
3.5 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5.1 General Lower Bound for Depth-2 HSTs . . . . . . . . . 42
3.5.2 Lower Bound for WFA on Depth-3 HSTs . . . . . . . . 45
3.6 Tight Bounds for WFA on the Line . . . . . . . . . . . . . . . . 59
3.7 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . 61

4 Competitive Algorithms for Generalized k-Server in Uniform

Metrics 63
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
 4.2 Deterministic Algorithm for Uniform Metrics . . . . . . . . . . 66
4.3 Randomized Algorithm for Uniform Metrics . . . . . . . . . . . 69
4.4 Algorithm for Weighted Uniform Metrics . . . . . . . . . . . . . 74
4.4.1 Algorithm Description . . . . . . . . . . . . . . . . . . . 75
4.4.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.5 Lower Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.6 Conclusion and Open Problems . . . . . . . . . . . . . . . . . . 80

Bibliography 83

Summary 89

Curriculum Vitae 91
Chapter 1

Introduction

1.1 Online Algorithms

In classical optimization, we are given a problem and a specific input, and the
goal is to find the optimal solution for the given input. However, in many
real life applications, the assumption that the whole input is available, is not
realistic. Most of the times, we need to solve optimization problems, while
taking decisions with incomplete information about the input. Below we list
some examples of such problems.

• Paging (Caching): This is a classical problem in operating systems

design. We are given a two-level memory system, composed by the cache
and the main memory. The cache is divided into k parts of equal size,
called pages, while the main memory has larger capacity, but it is much
slower. Whenever a page needs to be accessed by the CPU, it should
be in the cache; if it is not, a page fault occurs. The page needs to be
fetched in the cache, possibly by evicting some other page. Thus, any
operating system needs a page eviction policy. Here, the input can be
seen as a sequence of requests to pages, and the goal is to minimize the
number of page faults. In case all the requests are known in advance, it is
easy to find the optimal solution: Whenever a page eviction is needed, we
evict the page that will be requested the latest in the future. However,
in reality the future requests are not known, and the operating system
has to decide which page to evict taking into account only the requests
seen so far.

• Online Advertising: Consider a search engine like Google or Yahoo!.

Whenever a query is received, apart from the search results, some ads are
also displayed. Every day, for each ad there is a fixed number of times it
should appear, depending on the contract with the advertised business.

1
2 1. Introduction

For each query, the displayed ads should be targeted, so that there is a
good chance that the user will click on them. Clearly, if all the queries
of the day were known in advance, the search engine could choose which
ads to display to each query in order to maximize the expected revenue.
However, this information is not available, and whenever a user submits
a query, the search engine should decide immediately which ads to show.

• Vehicle Routing: Imagine a service provider with a certain number

of vehicles (e.g. taxis, firetrucks, ambulances, etc.). Whenever a client
needs a service, it submits a request, specifying a starting point and a
destination. The provider should send a vehicle to serve the request.
At the time a request is issued, there is no information about future
requests, and the provider should decide immediately which vehicle will
serve the request. The goal is to minimize the total distance traveled by
the vehicles.

All the examples above show problems where the input is not available
from the beginning, but it arrives over time and our goal is to optimize some
objective function. We call such problems online optimization problems, or
simply online problems. To solve problems in online optimization, we need to
devise algorithms which make decisions without knowledge of the future. We
call such algorithms online algorithms.

Model. Formally, in an online optimization problem the input σ is divided

into requests σ = σ1 , . . . , σm . Whenever each request σt is received, some acti-
ons must be performed, without knowledge of the future requests σt+1 , . . . , σm .
An algorithm that solves an online optimization problem is called an online
algorithm. An algorithm which reads the whole input σ and then produces a
solution is called an offline algorithm.

1.1.1 Competitive Analysis

The standard framework used to evaluate the performance of online algorithms
is competitive analysis, which was introduced by Sleator and Tarjan [66]. Here,
the performance of an online algorithm is compared to the optimal offline
solution which knows the whole input in advance.
From now on, we focus on minimization problems with computable optimal
solution, since this is the case for all problems considered in this thesis. Let P
be a minimization problem and let I denote the set of all valid inputs for P .
For an instance σ ∈ I, let OPT(σ) denote the optimal cost on σ. For an online
algorithm ALG, let ALG(σ) denote the cost of ALG on σ.
1.1. Online Algorithms 3

Definition 1.1. An online algorithm ALG for an online minimization problem

P is c-competitive if there exists a constant α such that for any input σ ∈ I,
we have that
ALG(σ) ≤ c · OPT(σ) + α.

If α = 0 we say that the algorithm ALG is strictly c-competitive [38]. The

competitive ratio of an algorithm ALG is the infimum value c such that ALG
is c-competitive. The competitive ratio of an online minimization problem P
is the infimum value c for which a c-competitive algorithm for P exists.
Note that there is no restriction on the computational resources used by
the online algorithm; the primary goal in competitive analysis is to to un-
derstand the importance of knowing the future. The competitive ratio of an
online problem is the loss factor due to lack of information, assuming unlimited
computational power. In practice, we seek efficient algorithms that achieve the
optimal or a nearly optimal competitive ratio.
An alternative view of competitive analysis is to think of each online pro-
blem as a game between an algorithm and an all-powerful adversary. The
adversary knows the description of the algorithm and constructs an input in
order to maximize the ratio between the cost of the algorithm and the optimal
cost.
Randomized Algorithms: A usual approach in the design of online al-
gorithms is to use randomization. In competitive analysis, there are various
adversary models proposed to evaluate randomized algorithms.
Oblivious Adversaries: In this model, the adversary knows the description
of the algorithm, but it does not know its random choices and it has to construct
the whole input before the algorithm starts serving the requests. A randomized
online algorithm ALG for a minimization problem P is c-competitive against
oblivious adversaries if there exists a constant α, such that for any request
sequence σ generated by an oblivious adversary, E[ALG(σ)] ≤ c · OPT(σ) + α.
Adaptive Online Adversaries: Here, the adversary knows all actions of the
algorithm, including its random choices. At each step, the adversary generates
a request in order to maximize the cost incurred by the algorithm. However,
the adversary must also serve the request sequence online. This way, the costs
of both the algorithm and the adversary depend on the random choices of the
algorithm. A randomized online algorithm ALG for a minimization problem P
is c-competitive against adaptive online adversaries, if there exists a constant α,
such that for any request sequence σ generated by an adaptive online adversary
ADV, E[ALG(σ)] ≤ c · E[ADV(σ)] + α, where ADV(σ) is the cost of ADV to
serve σ.
Typically the oblivious adversary model allows improved competitive ratios
compared to deterministic algorithms. For the rest of this thesis we focus on the
4 1. Introduction

oblivious adversary model, unless stated otherwise. We refer the reader to [18]
for a more detailed discussion on different adversary models for randomized
algorithms and connections between them.
An excellent reference on competitive analysis is [19].

1.1.2 Metrical Task Systems

Competitive analysis has been used to analyze online algorithms for many
important online problems. Initially, each problem was solved in a rather
ad-hoc way, using problem-specific techniques. In order to create a unifying
framework that enables the study of online algorithms in a systematic way,
Borodin et al. [20] defined the problem of metrical task systems (MTS), which
is a great generalization of various well-studied online problems.
In the MTS problem we are given a server which can be in one of N
different states and a metric distance function d specifying the cost of switching
between the states. At each time step, a task r arrives, represented by a vector
r = (r1 , . . . , rN ), where ri is the cost of processing r at state i. The server has
to decide in which state it will process the task. If it switches from state i to
state j and processes the task there, it incurs a cost d(i, j)+rj . Given an initial
state and a sequence of tasks, the goal is to process all tasks at minimum cost.
Metrical Service Systems (MSS): In [32, 31, 57] a slight restriction of the
MTS model was introduced, called metrical service systems (MSS)1 . Here, each
component of each task vector is either 0 or ∞. Therefore, each task can be
processed only in a subset of the states, whose coefficient is 0 (we call them
feasible states for this task).
It is easy to see that the paging problem is a special case of both MTS and
MSS: states correspond to all possible sets of pages in the cache and the cost
of switching between states equals the number of different pages between the
corresponding sets. Whenever a page p is requested, all the states that contain
p in the cache are feasible and the rest of the states are infeasible. Other notable
special cases of MTS include fundamental data structure problems such as the
list update problem [66, 62, 2] and the binary search tree problem [67, 3, 46].
In the general case, i.e. when the task vectors are arbitrary, the determinis-
tic competitive ratio is 2N −1 for MTS [20] and N −1 for MSS [57]. For rando-
mized algorithms the competitive ratio of both problems is O(log2 N log log N )
[40] and Ω(log N ) [20].
All problems considered in the rest of this thesis are special cases of MTS
and MSS with special structure, where usually a competitive ratio independent
of the number of states is possible.
1
In [57] it was called forcing task systems.
1.1. Online Algorithms 5

1.1.3 The k-Server Problem

The k-server problem is one of the most important and well-studied special
cases of the MTS and MSS problems. It was introduced by Manasse et al. [57]
as a far-reaching generalization of various online problems, the most notable
of which is the paging problem. The study of the k-server problem has led to
various remarkable developments in competitive analysis. One of the reasons
is its intriguing level of generality: on the one hand it is a special case of MSS
where a competitive ratio independent of the number of states can be achieved,
on the other hand it is a generalization of many online problems and requires
the development of generic and powerful techniques for online algorithms.
Formally, the k-server problem is defined in a metric space M = (U, d),
where U is a set of n points and d : U 2 → R is a (non-negative, symmetric)
distance function which satisfies the triangle inequality. There are k mobile
servers located at some points of the metric space. The input is a request
sequence σ = σ1 , σ2 , . . . , σm , where σt ∈ U is the point requested at time t. To
serve the request, some server must move at σt . The goal is to minimize the
total distance traveled by the servers for serving σ.

Connection with MSS and
paging. Note that the k-server problem can be
viewed as a MSS on N = nk states corresponding to all possible configurations
of the k servers. The distance between two states equals the minimum cost
perfect matching between the corresponding configurations. For each request,
the set of feasible MSS states corresponds to all configurations which have a
server at the requested point.
The paging problem is the special case of the k-server problem in a uniform
metric, i.e. when all distances between distinct points are 1. Here, the k-servers
correspond to the k slots in the cache, and the pages correspond to the points.
Evicting a page from the cache and bringing a new one maps to moving a
server between the corresponding points at a cost of 1. Equivalently, we can
think of a uniform metric as a star graph on n leaves corresponding to the n
pages, where all edges have length 1/2.

Background. In their seminal paper, Manasse et al. [57] showed that the
competitive ratio of deterministic algorithms is at least k, even if the metric
space contains n = k+1 points. For the paging problem, Sleator and Tarjan [66]
showed that many natural algorithms are k-competitive. Manasse et al. [57]
conjectured that this competitive ratio can be achieved in any metric space.

Conjecture 1.2 (The k-Server Conjecture). For any metric space, there exists
a k-competitive deterministic online algorithm.
6 1. Introduction

Qualitatively, this means that general metrics are believed to be no harder

than the simplest possible case of uniform metrics. The k-server conjecture at-
tracted a lot of attention and it has influenced the research on online algorithms
over the last three decades.

At the time the k-server conjecture was posed, it was not even known
whether a competitive ratio f (k) depending only on k is possible for general
metric spaces. The initial research focused on special metrics like weighted
stars, lines and trees, and for many cases tight k-competitive algorithms were
obtained [29, 30, 42, 54] (we discuss some of those results in detail in Chapter 2).

For general metric spaces, Fiat et al. [41] obtained the first f (k)-competitive
algorithm, with competitive ratio O((k!)3 ). Several improvements followed [5,
44, 18], but the ratio was still exponential in k. Then, in a breakthrough result,
Koutsoupias and Papadimitriou [53] showed that the Work Function Algorithm
(WFA) is (2k − 1)-competitive for every metric space, almost resolving the
conjecture. This remains up to date the best known upper bound on the
competitive ratio of the k-server problem.

We refer the reader to [19, 52] for an extensive treatment of the large body
of work on the k-server conjecture.

Randomized Algorithms: Typically, using randomization, an exponential

improvement on the competitive ratio is possible. However, randomized online
algorithms are not well understood compared to the deterministic ones.

For the k-server problem, it is believed that, similarly to the determi-

nistic case, the distance function does not affect the competitive ratio and
an O(log k)-competitive randomized algorithm against oblivious adversaries is
possible in any metric space (the so-called randomized k-server conjecture).
However, this is known to be true only for very special cases. In particular,
for the paging problem several O(log k)-competitive randomized algorithms are
known [1, 39, 59]. Nevertheless, even the simple generalization of the weighted
paging problem (which corresponds to the k-server problem on weighted star
graphs) remained open for almost two decades, until Bansal et al. [8] gave an
O(log k)-competitive algorithm using the primal-dual method.

More recently, polylog(k, n) competitive ratios for general metric spaces

were obtained [6, 21]. Those bounds are better than the deterministic compe-
titive ratio 2k − 1 in case n is sub-exponential in k. The techniques developed
in those works imply an O(log k)-competitive randomized algorithm for hier-
archically separated trees (HSTs – defined formally in Chapter 3) of constant
depth. Very recently, an O(log6 k)-competitive algorithm for any metric space
was claimed [56].
1.2. The (h, k)-Server Problem 7

1.2 The (h, k)-Server Problem

While the work on the k-server problem has been quite influential in the de-
velopment of competitive analysis, it also reveals some of its drawbacks. The
assumption that the input is created by a spiteful adversary is too pessimis-
tic and might enable strong lower bounds on the competitive ratio. For the
k-server problem, the competitive ratio grows linearly with k. That means,
when the number of servers k increases, the competitive ratio worsens. In-
tuitively, when the resources of the online algorithm increase, we expect its
performance to improve. This can not be captured by competitive analysis,
since the cost of the algorithm is compared to the optimal solution with the
same number of servers.

Resource Augmentation. A well-known approach to overcome the pes-

simistic lower bounds for online algorithms is called resource augmentation.
Here, we assume that the online algorithm is provided with some extra re-
sources, which are not available for the adversary. This approach has led to
spectacular success in online scheduling problems, see e.g. [50, 61, 14, 25].
In the context of the k-server problem, the resource augmentation is defined
by providing more servers to the online algorithm than the adversary. In
particular, the online algorithm has k servers, but its performance is compared
to an offline optimal algorithm with h ≤ k servers. This is called the (h, k)-
server problem, also known as the weak adversaries model for the k-server
problem [51].

Previous Work. In their seminal paper [66], Sleator and Tarjan gave several
k
k−h+1 -competitive algorithms for uniform metrics (the (h, k)-paging problem)
and also showed that this is the best possible ratio. This bound was later
extended to the weighted star metric (weighted paging) [68]. Note that this
guarantee equals k for k = h (the usual k-server setting), and tends to 1 as
k/h approaches infinity. In particular, for k = 2h, this is smaller than 2.
This shows that the resource augmentation model gives a more accurate
interpretation on the performance of online algorithms: The competitive ratio
improves substantially when the number of servers grows.
Interestingly, in contrast to the classic k-server problem, the (h, k)-server
problem is not well understood beyond uniform metrics. Prior to our work,
no o(h)-competitive algorithm was known, even for very simple extensions of
the weighted star, like trees of depth 2. In particular, for k  h it was not
even known whether using k servers any better performance can be achieved
compared to simply disabling the extra k − h servers and run the standard
k-server algorithms using only h servers.
8 1. Introduction

Our Contribution. In this thesis we initiate a systematic study of the (h, k)-
server problem. In Chapter 2, we focus on the (h, k)-server problem in the
euclidean line and in trees. We consider the Double Coverage (DC) algorithm,
which is known to be k-competitive for the standard k-server problem in those
metric spaces. We show that, surprisingly, its performance does not improve
as k increases, and its competitive ratio is exactly k(h+1)
k+1 . Note that this ratio
equals h for k = h and tends to h + 1 as k grows.
In Chapter 3, we consider trees of bounded depth. We show that the
previously known k-server algorithms (DC and WFA) do not improve as k
increases and they have competitive ratio Ω(h). Furthermore, we design a
new algorithm which is O(1)-competitive for trees of constant depth, whenever
k = (1 + )h for any  > 0. This gives the first o(h)-competitive algorithm for
any metric space other than the weighted star. Finally, we give a general lower
bound that any deterministic online algorithm has competitive ratio at least
2.4, even for trees of depth 2 and when k/h is arbitrarily large. This gives a
surprising qualitative separation between trees of depth 1 (weighted star) and
trees of depth 2 for the (h, k)-server problem.

Note on joint work. Chapter 2 is based on joint work with Nikhil Bansal,
Marek Eliáš, Lukasz Jeż and Kirk Pruhs, which is published in Theory of Com-
puting Systems [11]. A preliminary version of this work appeared in the 13th
International Workshop on Approximation and Online Algorithms (WAOA),
2015 [10]. Chapter 3 is based on joint work with Nikhil Bansal, Marek Eliáš
and Lukasz Jeż. A preliminary version of this work appeared in the 28th
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2017 [9].

1.3 The Generalized k-Server Problem

The study of the k-server problem has been essential in the development of
powerful techniques for online algorithms. For example, the landmark result
of Koutsoupias and Papadimitriou [53] on the k-server conjecture enabled the
belief that the WFA (or the generalized WFA [24]) performs optimally for any
metrical task system. Furthermore, the work on randomized k-server algo-
rithms enabled the development of powerful techniques using the primal-dual
method [23, 22, 7, 6] and more recently the mirror descent method [21].
Despite this progress, several natural variants and generalizations of the
k-server problem are very poorly understood. In particular, they exhibit very
different and intriguing behavior and the techniques for the standard k-server
problem do not seem to apply to them. Getting a better understanding of
such problems is a natural step towards building a deeper theory of online
computation. Below we list some examples of server problems that are not
1.3. The Generalized k-Server Problem 9

captured by the standard k-server model:

• The weighted k-server problem [60]. Here servers have different
weights w1 , . . . , wk and the cost of moving the ith server by distance d
is wi · d. This problem is substantially different from the (unweighted)
k-server problem. To get a feel for the problem, for uniform metrics the
Θ(k)
competitive ratio is 22 [43, 27, 12], and no competitive algorithms are
known for general metrics.
• The CNN problem [55]. In this problem we are given two servers in
the euclidean plane, the one moving in the horizontal axis and the other
in the vertical axis. At each time step a point (r1 , r2 ) is requested, and
in order to serve the request we should either move the horizontal server
to point x = r1 or the vertical server to y = r2 . This problem models
the movement of the crew of a news network in Manhattan: whenever
an event occurs, a camera should be either in the same street or in the
same avenue.
Motivated by all those variants of the k-server problem, Koutsoupias and
Taylor [55] introduced a substantial generalization of the k-server problem,
called the generalized k-server problem 2 . Here, each server si lies in its own
metric space Mi , with its own distance function di . A request is a k-tuple
r = (r1 , r2 , . . . , rk ) and must be served by moving some server si to the point
ri ∈ Mi .
Note that the standard k-server problem corresponds to the special case
when all the metrics are identical, M1 = . . . = Mk = M , and the requests are of
the form (r, r, . . . , r), i.e., the k-tuple is identical in each coordinate. Similarly,
the weighted k-server problem corresponds to the case when the metric spaces
are scaled copies of each other, i.e. Mi = wi · M for some fixed M , and the
requests have the form (r, . . . , r). Finally, the CNN problem corresponds to
the case where k = 2 and both M1 , M2 are lines.

Previous Work. Despite the intense interest, this problem is poorly un-
derstood. Prior to our work, competitive algorithms were known only for
k = 2 [65, 63]. Sitters [63] highlights that the existence of an f (k)-competitive
algorithm is among the most intriguing and important open problems in online
computation.

Our Contribution. In Chapter 4, we consider the generalized k-server pro-

blem on uniform metrics and obtain the first f (k)-competitive algorithms for
general k, whose competitive ratios almost match the known lower bounds.
2
In fact, Koutsoupias and Taylor called the problem “sum of k 1-server problems”. The
name generalized k-server was proposed by Sitters and Stougie [65].
10 1. Introduction

Note on joint work. The results in Chapter 4 are based on joint work with
Nikhil Bansal, Marek Eliáš and Jesper Nederlof, which appeared in the 29th
ACM-SIAM Symposium on Discrete Algorithms (SODA), 2018 [13].
Chapter 2

Tight Bounds for Double

Coverage Against Weak
Adversaries

2.1 Introduction
In this chapter we study the Double Coverage (DC) algorithm for the (h, k)-
server problem. It is well-known that DC is k-competitive for h = k in any
tree metric. We prove that even if k > h the competitive ratio of DC does not
improve; in fact, it increases up to h + 1 as k grows. In particular, we show
matching upper and lower bounds of k(h+1)
k+1 on the competitive ratio of DC in
tree metrics.

Related Work. The k-server problem is a far reaching generalization of

various online problems. The most well-studied of those is the paging (caching)
problem, which corresponds to k-server problem on a uniform metric space.
Sleator and Tarjan [66] gave several k-competitive algorithms for paging and
showed that this is the best possible ratio for any deterministic algorithm.
Interestingly, the k-server problem does not seem to get harder in more ge-
neral metrics. The celebrated k-server conjecture states that a k-competitive
deterministic algorithm exists for every metric space. Koutsoupias and Papa-
dimitriou [53] showed that the Work Function Algorithm (WFA) is (2k − 1)-
competitive for every metric space, almost resolving the conjecture. The
conjecture has been settled for several special metrics (an excellent reference
is [19]). In particular for the line metric, Chrobak et al. [29] gave an elegant k-
competitive algorithm called Double Coverage (DC). This algorithm was later
extended and shown to be k-competitive for all tree metrics [30]. Additionally,
in [17] it was shown that the WFA is k-competitive for some special metrics,

11
12 2. Tight Bounds for Double Coverage Against Weak Adversaries

including the line.

The (h, k)-server problem: In the (h, k)-setting, the online algorithm has
k servers, but its performance is compared to an offline optimal algorithm
with h ≤ k servers. The (h, k)-server setting turns out to be much more
intriguing and is much less understood than the standard k-server. For uniform
metrics (the (h, k)-paging problem), k/(k − h + 1)-competitive algorithms are
known [66] and no deterministic algorithm can achieve a better ratio. Note
that this guarantee equals k for h = k, and tends to 1 as the ratio k/h becomes
arbitrarily large. In particular, for k = 2h, this is smaller than 2. The same
competitive ratio can also be achieved for the weighted caching problem [68],
which is equivalent to the (h, k)-server problem on weighted stars (and even
for the more general file caching problem [69], which is not a special case of
the (h, k)-server problem).
It might seem natural to conjecture that, analogously to the k-server case,
general metrics are no harder than the uniform metrics, and hence that k/(k −
h + 1) is the right bound for the (h, k)-server problem in all metrics. However,
surprisingly, Bar-Noy and Schieber (cf. [19, p. 175]) showed this to be false:
In the line metric, for h = 2, no deterministic algorithm can be better than
2-competitive, regardless of the value of k. This is the best known lower bound
for the general (h, k)-server problem.
On the other hand, the best known upper bound is 2h, even when k/h → ∞.
In particular, Koutsoupias [51] showed that the WFA with k servers is 2h-
competitive1 against an offline optimum with h servers. Note that one way to
achieve a guarantee of 2h − 1 is simply to disable the k − h extra online servers
and use WFA with h servers only. The interesting thing about the result
of [51] is that the online algorithm does not know h and is 2h-competitive
simultaneously for every h ≤ k. But, even if we ignore this issue of whether
the online algorithm knows h or not, no guarantee better than h is known,
even for very special metrics such as depth-2 HSTs or the line, and even when
k/h → ∞.

The DC algorithm: This situation motivates us to consider the (h, k)-server

problem on the line and more generally on trees. In particular, we consider
the Double Coverage (DC) algorithm [29] originally defined for a line, and its
generalization to trees [30]. We call an algorithm’s server s adjacent to the
request r if there are no algorithm’s servers on the unique path between the
locations of r and s. Note that there may be multiple servers in one location,
satisfying this requirement — in such case, one of them is chosen arbitrarily
1
Actually, [51] gives a stronger bound: WFAk ≤ 2h · OPTh − OPTk + O(1), where the
algorithm’s subscripts specify how many servers they use.
2.1. Introduction 13

as the adjacent server for this location, and the others are considered non-
adjacent.
DC-Line: If the current request r lies outside the convex hull of current loca-
tions of the servers, serve it with the nearest server. Otherwise, we move the
two servers adjacent to r towards it at equal speed until some server reaches r.
DC-Tree: We move all the servers adjacent to r towards it at equal speed until
some server reaches r. Note that the set of servers adjacent to r can change
during the move, in particular when some server reaches a vertex of the tree.
We call the parts of the move where the set of adjacent servers stays the same
elementary moves.
There are several natural reasons to consider DC for the line and trees. For
paging (and weighted paging), all known k-competitive algorithms also attain
the optimal ratio for the (h, k) version. This suggests that a k-competitive
algorithm for the k-server problem might attain the “right” ratio in the (h, k)-
setting. DC is the only deterministic k-server algorithm known to be k-
competitive for the line and trees. Moreover, DC obtains the optimum k/(k −
h+1)-competitive ratio for the (h, k)-paging problem, as we show2 in Section 2.5.

Our Results: We show that the exact competitive ratio of DC on lines and
trees in the (h, k)-setting is k(h+1)
(k+1) .

k(h+1)
Theorem 2.1. The competitive ratio of DC is at least (k+1) , even for a line.
Note that for a fixed h, the competitive ratio worsens slightly as the num-
ber of online servers k increases. In particular, it equals h for k = h and it
approaches h + 1 as k → ∞.
Consider the seemingly trivial case of h = 1. If k = 1, clearly DC is 1-
competitive. However, for k = 2 it becomes 4/3 competitive, as we now sketch.
Consider the instance where all servers are at x = 0 initially. A request arrives
at x = 2, upon which both DC and offline move a server there and pay 2.
Then a request arrives at x = 1. DC moves both servers there and pays 2
while offline pays 1. All servers are now at x = 1, and the instance repeats.
Generalizing this example to (1, k) already becomes quite involved. Our
lower bound in Theorem 2.1 for general h and k is based on an adversarial
strategy obtained by a careful recursive construction.
We also give a matching upper bound.
k(h+1)
Theorem 2.2. For any tree, the competitive ratio of DC is at most (k+1) .
2
This was known implicitly since the work of Chrobak and Larmore [30], where it was
pointed out that DC in star metrics is equivalent to Flush-When-Full (FWF) algorithm, and
it is well-known that FWF attains the optimal competitive ratio. In Section 2.5 we give an
explicit proof.
14 2. Tight Bounds for Double Coverage Against Weak Adversaries

request
L R
qL qR
δ δ
Figure 2.1: DC server is pulled to the right by δ

This generalizes the previous results for h = k [29, 30]. Our proof also
follows similar ideas, but our potential function is more involved (it has three
terms instead of two), and the analysis is more subtle. To keep the main ideas
clear, we first prove Theorem 2.2 for the simpler case of a line in Section 2.3.
The proof for trees is analogous but more involved, and is described in Section
2.4.

2.2 Lower Bound

We now prove Theorem 2.1. We will describe an adversarial strategy Sk for
the setting where DC has k servers and the offline optimum (adversary) has h
servers, whose analysis establishes that the competitive ratio of DC is at least
k(h + 1)/(k + 1).
Roughly speaking (and ignoring some details), the strategy Sk works as
follows. Let I = [0, bk ] be the working interval associated with Sk . Let L =
[0, bk ] and R = [(1 − )bk , bk ] denote the (tiny) left front and right front of I.
Initially, all offline and online servers are located in L. The adversary moves all
its h servers to R and starts requesting points in R, until DC eventually moves
all its servers to R. The strategy inside R is defined recursively depending
on the number of DC servers currently in R: if DC has i servers in R, the
adversary executes the strategy Si repeatedly inside R, until another DC server
arrives there, at which point it switches to the strategy Si+1 . When all DC
servers reach R, the adversary moves all its h servers back to L and repeats
the symmetric version of the above instance until all servers move from R to L.
This defines a phase. To show the desired lower bound, we recursively bound
the online and offline costs during a phase of Sk in terms of costs incurred by
strategies S1 , S2 , . . . , Sk−1 .
A crucial parameter of a strategy will be the pull. Recall that DC moves
some server qL closer to R if and only if qL is the rightmost DC server outside
R and a request is placed to the left of qR , the leftmost DC server in R, as
shown in Figure 2.1. In this situation qR moves by δ to the left and qL moves
to the right by the same distance, and we say that the strategy in R exerts
a pull of δ on qL . We will be interested in the amount of pull exerted by a
strategy during one phase.
2.2. Lower Bound 15

Sk
•
L R
Sk−1• •.Sk−1
.. ..
Sh+2 •. •Sh+2
L R L R
Sh+1• • • •Sh+1
L R L R
Sh• •• •• •• •Sh

Figure 2.2: Representation of strategies and the areas that they define using a
binary tree.

Formal description: We now give a formal definition of the instance. We

begin by introducing the quantities (that we bound later) associated with each
strategy Si during a single phase:
• di , lower bound for the cost of DC inside the working interval.

• Ai , upper bound for the cost of the adversary.

• pi , Pi , lower resp. upper bound for the “pull” exerted on any external
DC servers located to the left of the working interval of Si . Note that,
as will be clear later, by symmetry the same pull is exerted to the right.
For i ≥ h, the ratio ri = Adii is a lower bound for the competitive ratio of DC
with i servers against an adversary with h servers.
We now define the right and left front precisely. Let ε > 0 be a sufficiently
small constant. For i ≥ h, we define the size of working intervals for strategy Si
as sh := h and si+1 := si /ε. Note that sk = h/εk−h . The working interval for
strategy Sk is [0, sk ], and inside it we have two working intervals for strategies
Sk−1 : [0, sk−1 ] and [sk −sk−1 , sk ]. We continue this construction recursively and
the nesting of these intervals creates a tree-like structure as shown in Figure
2.2. For i ≥ h, the working intervals for strategy Si are called type-i intervals.
Strategies Si , for i ≤ h, are special and are executed in type-h intervals.

Strategies Si for i ≤ h: For i ≤ h, strategies Si are performed in a type-h

interval (recall this has length h). Let Q be h + 1 points in such an interval,
with distance 1 between consecutive points.
→ ← →
There are two variants of Si that we call Si and Si . We describe Si in
←
detail, and the construction of Si will be exactly symmetric. At the beginning
→
of Si , we ensure that DC servers occupy the rightmost i points of Q and
adversary servers occupy the rightmost h points of Q as shown in Figure 2.3.
16 2. Tight Bounds for Double Coverage Against Weak Adversaries

qh+1 qh ... q4 q3 q2 q1
points of Q
servers of adversary
servers of DC

→
Figure 2.3: The initial position for Strategy S3 (for h ≥ 3), in which the
adversary requests q4 , q3 , q2 , q1 . DC’s servers move for a total of 6, exerting a
pull of 1 in the process, only to return to the same position. The adversary’s
cost is 0 if h > 3 and 2 if h = 3: in such case, the adversary serves both q4 and
q3 with the server initially located in q3 .

The adversary requests the sequence qi+1 , qi , . . . , q1 . It is easily verified that

DC incurs cost di = 2i, and its servers return to the initial position qi , . . . , q1 ,
→
so we can iterate Si again. Moreover, a pull of pi = 1 = Pi is exerted in both
directions.
For i < h, the adversary does not have to move at all, thus Ai = 0. For
i = h, the offline can serve the sequence with cost Ah = 2, by using the server
in qh to serve request in qh+1 and then moving it back to qh .
←
For strategy Si , we just number the points of Q in the opposite direction
(q1 will be leftmost and qh+1 rightmost). The request sequence, analysis, and
assumptions about initial position are the same.

Strategies Si for i > h: We define the strategy Si for i > h, assuming that
S1 , . . . , Si−1 are already defined. Let I denote the working interval for Si . We
assume that, initially, all offline and DC servers lie in the leftmost (or analo-
gously rightmost) type-(i − 1) interval of I. Indeed, for Sk this is achieved by
the initial configuration, and for i < k we will ensure this condition before ap-
plying strategy Si . In this case our phase consists of left-to-right step followed
by right-to-left step (analogously, if all servers start in the rightmost interval,
we apply first right-to-left step followed by left-to-right step to complete the
phase).
For each h ≤ j < i, let Lj and Rj denote the leftmost and the rightmost
type-j interval contained in I respectively.
Left-to-right step:

1. The adversary moves all its servers from Li−1 to Rh , specifically to the
→
points q1 , . . . , qh to prepare for the strategy S1 . Next, point q1 is reque-
sted, which forces DC to move one server to q1 , thus satisfying the initial
→
conditions of S1 . The figure below illustrates the servers’ positions after
these moves are performed.
2.2. Lower Bound 17

request
Li−1 Ri−1 qh+1 DC
q1
Si
ADV
Lh Rh
Rh+1

→
2. For j = 1 to h: Apply S j to interval Rh until the (j + 1)-th server of DC
→
arrives at the point qj+1 of Rh . Then, complete the request sequence Sj ,
so that DC servers will reside in points qj+1 , . . . , q1 , ready for strategy
→
Sj+1 . The figure below illustrates the servers’ positions after all those
moves (i.e., the whole outer loop, for j = 1 . . . , h) are performed.
request
Li−1 Ri−1 qh+1 DC
q1
Si
ADV
Rh
Rh+1

3. For j = h + 1 to i − 1: keep applying Sj to interval Rj until the (j + 1)-th

→ ←
server arrives in Rj . To clarify, Sj stands for either Sj or Sj , depending
on the locations of servers within Rj . In particular, the first Sj for any
←
j is Sj . Note that there is exactly one DC server in the working interval
of Si moving toward Rj from the left: the other servers in that working
interval are either still in Li−1 or in Rj . Since Rj is the rightmost interval
of Rj+1 and Li−1 ∩ Rj+1 = ∅, the resulting configuration is ready for
←
strategy Sj+1 . The figure below illustrates the very beginning of this
sequence of moves, for j = h + 1, right after the execution of the first
←
step (of this three-step description) of Sj+1 .
request
Li−1 Ri−1 DC
Si
ADV

Rh+1

→ ←
Right-to-left step: Same as Left-to-right, just replace Sj by Sj , Rj intervals by
Lj , and Lj by Rj .

Bounding Costs: We begin with a simple but useful observation that follows
directly from the definition of DC. For any subset X of i ≤ k consecutive DC
servers, let us call center of mass of X the average position of servers in X.
We call a request external with respect to X, when it is outside the convex
hull of X and internal otherwise.
18 2. Tight Bounds for Double Coverage Against Weak Adversaries

Lemma 2.3. For any sequence of internal requests with respect to X, the
center of mass of X remains the same.
Proof. Follows trivially since for any internal request, DC moves precisely two
servers towards it, by an equal amount in opposite directions.

Let us derive bounds on di , Ai , pi , and Pi in terms of these quantities for

j < i. First, we claim that the cost Ai incurred by the adversary for strategy
Si during a phase can be upper bounded as follows:
 i−1   i−1 
X si X Aj
Ai ≤ 2 si h + Aj = 2si h + (2.1)
pj pj
j=1 j=h

In the inequality above, we take the cost for left-to-right step multiplied by
2, since left-to-right and right-to-left step are symmetric. The term si h is the
cost incurred by the adversary in the beginning of the step, when moving all its
servers from the left side of I to the right. The costs Aj psji are incurred during
the phases of Sj for j = 1, . . . , i − 1, because Aj is an upper bound on the cost
of the adversary during a phase of strategy Sj and psji is an upper bound on
the number of phases of Sj during Si . This follows because Sj (during left to
right phase) executes as long as the (j + 1)-th server moves from left of I to
right of I. It travels a distance of at most si and receives a pull of pj during
each iteration of Sj in R. Finally, the equality in (2.1) follows, as Aj = 0 for
j < h.
We now lower bound the cost of DC. Let us denote δ := (1 − 2ε). The
length of I \ (Li−1 ∪ Ri−1 ) is δsi and all DC servers moving from right to left
δs
have to travel at least this distance. Furthermore, as Pjj is a lower bound for
the number of iterations of strategy Sj , we obtain:
 i−1   i−1 
X δsi X dj
di ≥ 2 δsi i + dj = 2δsi i + (2.2)
Pj Pj
j=1 j=1

It remains to show the upper and lower bounds on the pull Pi and pi exerted
on external servers due to the (right-to-left step of) strategy Si . Suppose Si
is being executed in interval I. Let x denote the closest DC server strictly to
the left of I. Let X denote the set containing x and all DC servers located
in I. During the right-to-left step of Si , all requests are internal with respect
to X. So by Lemma 2.3, the center of the mass of X remains unchanged. As
i servers moved from right to left during right-to-left step of Si , this implies
that x should have been pulled to the left by the same total amount, which is
at least iδsi and at most isi . Hence,

Pi := isi pi := iδsi (2.3)

2.2. Lower Bound 19

Due to a symmetric argument, during the left-to-right step, the same amount
of pull is exerted to the right.
Now we are ready to prove Theorem 2.1.

Proof of Theorem 2.1. The proof is by induction. In particular, we will show

that the following holds for each i ∈ [h, k]:

di Ai 2(i + 1) −(i−h)
≥ 2iδ i−h and ≤ δ (2.4)
Pi pi h+1

Setting i = k, this implies the theorem as the competitive ratio rk of DC

satisfies

dk dk /Pk 2k δ k−h k(h + 1) 2(k−h)

rk ≥ ≥ ≥ = δ .
Ak Ak /pk 2(k+1) δ −(k−h) k+1
h+1

k(h+1)
Therefore, as δ = (1 − 2ε), it is easy to see that rk → k+1 when ε → 0:

Induction base (i = h): For the base case we have ah = 2, dh = 2h, and
ph = Ph = 1, so Pdhh = 2h and Aphh = 2, i.e., (2.4) holds.

Induction step (i > h): Using (2.2), (2.3), and induction hypothesis, we
obtain
 i−1   i−1 
di 2δ X dj 2δ X
j−h 2δ
≥ i+ ≥ i+ 2jδ ≥ δ i−1−h (i + i(i − 1)) = 2iδ i−h ,
Pi i Pj i i
j=1 j=1

Pi−1
where the last inequality follows from the fact that j=1 2j = i(i − 1). Simi-
larly, we prove the second part of (2.4). The first inequality follows from (2.1)
and (2.3), the second from the induction hypothesis:
 i−1   i−1 
Ai 2 X Aj 2 X 2(j + 1) −(j−h)
≤ h+ ≤ h+ δ
pi iδ pj iδ h+1
j=h j=h
Pi−1
2 −(i−1−h) h(h + 1) + 2 j=h (j + 1)
 
≤ δ
iδ h+1
2 i(i + 1) 2(i + 1) −(i−h)
≤ i−h = δ ,
iδ h+1 h+1
Pi−1
The last inequality follows from 2 j=h (j + 1) = i(i + 1) − h(h + 1).
20 2. Tight Bounds for Double Coverage Against Weak Adversaries

2.3 Upper Bound

In this section, we give an upper bound on the competitive ratio of DC that
matches the lower bound from the previous section.
We begin by introducing some notation. We denote the optimal offline
algorithm by OPT. Let r be a request issued at time t. Let X denote the
configuration of DC (i.e. the multiset of points in the line where DC servers
are located) and Y the configuration of OPT before serving request r. Similarly,
let X 0 and Y 0 be the corresponding configurations after serving r.
In order to prove our upper bound, we will define a potential function
Φ(X, Y ) such that

DC(t) + Φ(X 0 , Y 0 ) − Φ(X, Y ) ≤ c · OP T (t), (2.5)

where c = k(h+1)
k+1 is the desired competitive ratio, and DC(t) and OP T (t)
denote the cost incurred by DC and OPT at time t. Coming up with a potential
function Φ that satisfies (2.5) is sufficient, as c-competitiveness follows from
summing this inequality over time.
For a set of points A, let DA denote the sum of all |A|


2 pairwise distances
between points in A. Let M ⊆ X be some fixed set of h servers of DC and
M(M, Y ) denote the minimum weight perfect matching between M and Y ,
where the weights are determined by the distances. Abusing the notation
slightly, we will denote by M(M, Y ) both the matching and its cost. We
denote
k(h + 1) k
ΨM (X, Y ) := · M(M, Y ) + · DM .
k+1 k+1
Then the potential function is defined as follows:
1
Φ(X, Y ) = min ΨM (X, Y ) + · DX
M
 k+1 
k(h + 1) k 1
= min · M(M, Y ) + · DM + · DX .
M k+1 k+1 k+1

Note that this generalizes the potential considered in [29, 30] for the case of
h = k. In that setting, all the online servers are matched and hence DM = DX
and is independent of M , and thus the potential above becomes k times that
minimum cost matching between X and Y plus Dx . On the other hand in our
setting, we need to select the right set M of DC servers to be matched to the
offline servers based on minimizing ΨM (X, Y ).
Let us first give a useful property concerning minimizers of Ψ, which will
be crucial later in our analysis. Note that ΨM (X, Y ) is not simply the best
matching between X and Y , but also includes the term DM which makes the
argument slightly subtle.
2.3. Upper Bound 21

Lemma 2.4. Let X and Y be the configurations of DC and OPT and consider
some fixed offline server at location y ∈ Y . There exists a minimizer M of Ψ
that contains some DC server x which is adjacent to y. Moreover, there is a
minimum cost matching M between M and Y that matches x to y.

We remark that the statement does not necessarily hold simultaneously for
every offline server, but only for a single fixed offline server y. Moreover, we
note that the adjacency in the lemma statement and the proof is defined as for
the DC algorithm (cf. Section 2.1); specifically, as if there was a request at y’s
position.

Proof of Lemma 2.4. Let M 0 be some minimizer of ΨM (X, Y ) and M0 be some

associated minimum cost matching between M 0 and Y . Let x0 denote the online
server currently matched to y in M0 and suppose that x0 is not adjacent to y.
Let x denote the server in X adjacent to y on the path from y to x0 .
We will show that we can always modify the matching (and M 0 ) without
increasing the cost of Φ, so that y is matched to x. We consider two cases
depending on whether x is matched or unmatched.

1. If x ∈ M 0 : Let y 0 denote the offline server which is matched to x in

M0 . To create new matching M, we swap the edges and match x to y
and x0 to y 0 . The cost of the edge connecting y in the matching reduces
by exactly d(x0 , y) − d(x, y) = d(x0 , x). On the other hand, the cost
of the matching edge for y 0 increases by d(x0 , y 0 ) − d(x, y 0 ) ≤ d(x, x0 ),
due to triangle inequality. Thus, the new matching has no larger cost.
Moreover, the set of matched servers does not change, i.e., M = M 0 , and
hence DM = DM 0 , which implies that ΨM (X, Y ) ≤ ΨM 0 (X, Y ).

2. If x ∈ / M 0 : In this case, we set M = M 0 \ {x0 } ∪ {x} and we form M,

where y is matched to x and all other offline servers are matched to
the same server as in M0 . Now, the cost of the matching reduces by
d(x0 , y) − d(x, y) = d(x, x0 ). Moreover, DM ≤ DM 0 + (h − 1) · d(x, x0 ),
as the distance of each server in M 0 \ {x0 } to x can be greater than the
distance to x0 by at most d(x, x0 ). This gives

(h + 1)k k(h − 1)
ΨM (X, Y ) − ΨM 0 (X, Y ) ≤ − · d(x, x0 ) + · d(x, x0 )
k+1 k+1
2k
=− · d(x, x0 ) < 0 ,
k+1

and hence ΨM (X, Y ) is strictly smaller than ΨM 0 (X, Y ).

We are now ready to prove Theorem 2.2 for the line.

22 2. Tight Bounds for Double Coverage Against Weak Adversaries

Proof. Recall, that we are at time t and request r is arriving. We divide the
analysis into two steps: (i) OPT serves r, and then (ii) DC serves r. As a
consequence, whenever a server of DC serves r, we can assume that a server of
OPT is already there.
For all following steps considered, M is the minimizer of ΨM (X, Y ) in the
beginning of the step. It might happen that, after change of X, Y during
the step, a better minimizer can be found. However, an upper bound for
∆ΨM (X, Y ) is sufficient to bound the change in the first term of the potential
function.

OPT moves: If OPT moves one of its servers by distance d to serve r, the
value of ΨM (X, Y ) increases by at most k(h+1)
k+1 d. As OP T (t) = d and X does
not change, it follows that
k(h + 1)
∆Φ(X, Y ) ≤ · OP T (t) ,
k+1
and hence (2.5) holds. We now consider the second step, when DC moves.

DC moves: We consider two cases depending on whether DC moves a single

server or two servers.

1. Suppose DC moves its rightmost server (the leftmost server case is iden-
tical) by distance d. Let y denote the offline server at r. By Lemma 2.4
we can assume that y is matched to the rightmost server of DC. Thus,
the cost of the minimum cost matching between M and Y decreases by d.
Moreover, DM increases by exactly (h − 1)d (as the distance to rightmost
server increases by d for all servers of DC). Thus, ΨM (X, Y ) changes by

k(h + 1) k(h − 1) 2k
− ·d+ ·d=− ·d .
k+1 k+1 k+1

Similarly, DX increases by exactly (k − 1)d. This gives us that

2k k−1
∆Φ(X, Y ) ≤ − ·d+ · d = −d .
k+1 k+1

As DC(t) = d, this implies that (2.5) holds.

2. We now consider the case when DC moves 2 servers x and x0 , each by

distance d. Let y denote the offline server at the request r. By Lemma 2.4
applied to y, we can assume that M contains at least one of x or x0 , and
that y is matched to one of them (say x) in some minimum cost matching
M of M to Y .
2.4. Extension to Trees 23

We note that DX decreases by precisely 2d. In particular, the distance

between x and x0 decreases by 2d, and for any other server of X\{x, x0 } its
total distance to other servers does not change. Moreover, DC(t) = 2d.
Hence, to prove (2.5), it suffices to show
k
∆ΨM (X, Y ) ≤ − · 2d . (2.6)
k+1
To this end, we consider two sub-cases.
(a) Both x and x0 are matched: In this case, the cost of the matching M
does not increase as the cost of the matching edge (x, y) decreases
by d and the move of x0 can increase the cost of the matching by
at most d. Moreover, DM decreases by precisely 2d (due to x and
x0 moving closer). Thus, ∆ΨM (X, Y ) ≤ − k+1 k
· 2d, and hence (2.6)
holds.
(b) Only x is matched (to y) and x0 is unmatched: In this case, the cost
of the matching M decreases by d. Moreover, DM can increase by
at most (h − 1)d, as x can move away from each server in M \ {x}
by distance at most d. So
(h + 1)k k(h − 1) 2k
∆ΨM (X, Y ) ≤ − ·d+ ·d=− ·d ,
k+1 k+1 k+1
i.e., (2.6) holds.

2.4 Extension to Trees

We now consider tree metrics. Specifically, we prove Theorem 2.2.
Part of the analysis carries over from the previous section. Observe that
Lemma 2.4 holds for trees: we only used the triangle inequality and the fact
that there exists a unique path between any two points. The main difference
in the proof is that the set of servers adjacent to the request can now have
arbitrary size (i.e., it no longer contains at most two servers) and that it can
change as the move is executed, see Figure 2.4. To cope with this, we analyze
elementary moves, as did Chrobak and Larmore [30]. Recall that an elementary
move is a part when the set of servers adjacent to the request remains fixed.

Proof of Theorem 2.2. We use the same potential as before, i.e, we let
k(h + 1) k
ΨM (X, Y ) := · M(M, Y ) + · DM ,
k+1 k+1
and define
1
Φ(X, Y ) = min ΨM (X, Y ) + · DX .
M k+1
24 2. Tight Bounds for Double Coverage Against Weak Adversaries

a1 v
a3
s
a2

Qa1 Qa2 Qa3

Figure 2.4: Beginning of elementary move: server a1 just covered server s

removing him from the set of servers adjacent to request r. Servers a1 , a2 , and
a3 will move towards r, until a3 reaches subroot v removing a2 from the list of
adjacent servers and completing thereby this elementary move.

To prove the theorem, we show that for any time t the following holds:

DC(t) + Φ(X 0 , Y 0 ) − Φ(X, Y ) ≤ c · OP T (t), (2.7)

where c = k(h+1)
k+1 .
As in the analysis for the line, we split the analysis in two parts: (i) OPT
serves r, and then (ii) DC serves r. As a consequence, whenever a server of
DC serves r, we can assume that a server of OPT is already there.

OPT moves: If OPT moves a server by distance d, only the matching cost
is affected in the potential function, and it can increase by at most d · k(h +
1)/(k + 1). Therefore

k(h + 1)
∆Φ(X, Y ) ≤ · OP T (t) ,
k+1

and hence (2.7) holds.

DC moves: Instead of focusing on the whole move done by DC to serve

request r, we prove that (2.7) holds for each elementary move.
Consider an elementary move where q servers are moving by distance d.
Let A denote the set of those active servers. Clearly, |A| = q. Let also M
be a minimizer of ΨM (X, Y ) at the beginning of the step. Let us imagine for
now, that the requested point r is the root of the whole tree. For a ∈ A let Qa
denote the set of DC servers in the subtree rooted at a’s location, including a,
see Figure 2.4. We set qa := |Qa | and ha := |Qa ∩M |. Finally, let AM := A∩M .
By Lemma 2.4, we can assume that one of the servers in A is matched
to the offline server in r. Thus the move of this server decreases the cost of
2.4. Extension to Trees 25

M(M, Y ) by d. The move of all other servers of AM can increase the cost of
M(M, Y ) by at most (|AM | − 1) · d. We get that

∆M(M, Y ) ≤ (|AM | − 2) · d .

In order to calculate the change in DX and DM , it is convenient to consider

the moves of active servers sequentially rather than simultaneously.
We start with DX . Clearly, each a ∈ A moves further away from qa − 1
servers in X by distance d and gets closer to the remaining k − qa ones by the
same distance. Thus, the change of DX associated with a is (qa −1−(k−qa ))d =
(2qa − k − 1)d. Therefore we have
X
∆DX = (2qa − k − 1)d = (2k − q(k + 1)) d ,
a∈A

P
as a∈A qa
= k.
Similarly, for DM , we first note that it can change only due to moves of
servers in AM . Specifically, each a ∈ AM moves further away from ha − 1
servers in M and gets closer to the remaining h − ha of them. Thus, the
change of DM associated with a is (2ha − h − 1)d. Therefore we have
X
∆DM = (2ha − h − 1)d ≤ (2h − |AM |(h + 1)) d ,
a∈AM

P P
since a∈AM ha ≤ a∈A ha = h.
Using above inequalities, we see that the change of potential is at most

k(h + 1)d k·d d

(|AM | − 2) + (2h − |AM |(h + 1)) + (2k − q(k + 1))
k+1 k+1 k+1
d

≤ k(h + 1)(|AM | − 2) + k (2h − |AM |(h + 1)) + 2k − q(k + 1)
k+1
d
= (−q(k + 1)) = −q · d ,
k+1

since

k(h + 1)(|AM | − 2) + k(2h − |AM |(h + 1)) + 2k

= −2k(h + 1) + k(h + 1)|AM | − |AM |k(h + 1) + 2kh + 2k
= −2k(h + 1) + 2k(h + 1) = 0

Thus, (2.7) holds, as DC(t) = q · d.

26 2. Tight Bounds for Double Coverage Against Weak Adversaries

2.5 Competitive Ratio of DC for the Paging Pro-

blem
The paging problem is the special case of the k-server on a star graph, where
all edges have weight 21 and all requests appear at the leaves. It known that
k
(h, k)-paging has a deterministic competitive ratio of k−h+1 . However, we are
not aware of any explicit proof showing that the DC algorithm also achieves
this ratio. We give such a proof using a potential function.
Let X and Y denote the configurations of DC and OPT respectively. Note
that any server of DC can only be at the root or at a leaf, and servers of OPT
can only be at leaves.
We define
−k − h + 1 k
Φ(t) = `+ |Y \ X|
2(k − h + 1) k−h+1
Where ` is the number of DC servers at the root.
Analysis: As usual, we consider separately moves of DC and OPT. We
assume that, whenever a point is requested, first OPT moves a server there
and then DC moves its servers.
Offline moves: When optimal moves any single server from one leaf to
another it pays 1. The first term of the potential is not affected while the
k k
second can increase by at most one. We get that ∆Φ ≤ k−h+1 = k−h+1 · OPT.
DC moves: Let us now consider moves of DC. We distinguish between two
cases depending on whether it moves one or more servers.
• ` > 0: In this case, DC moves one server from the root to the requested
leaf, so DC pays 1/2. The number of servers at the root ` decreases by 1
and the second term decreases by 1. We get
k+h−1 k −k + h − 1 1
∆Φ = − = =−
2(k − h + 1) k − h + 1 2(k − h + 1) 2
and hence DC + ∆Φ = 0.
• ` = 0: In the case, DC moves all the servers from the leaves toward the
root (and then we go to the case above). In that case DC occurs a cost of
k/2. Let us call a the number of online servers that coincide with servers
of OPT before the move of DC. Then ` is increasing by k while |Y \ X|
increases by a. We get that
−k − h + 1 k
∆Φ = k+ a
2(k − h + 1) k−h+1

Observe that a ≤ h − 1, as there is an OPT at the current request that

was not covered when DC started moving. Thus we can upper bound
∆Φ as:
2.5. Competitive Ratio of DC for the Paging Problem 27

−k − h + 1 + 2(h − 1) −k + h − 1
∆Φ ≤ k= k
2(k − h + 1) 2(k − h + 1)
k−h+1 k
− k=− .
2(k − h + 1) 2

k k
Overall we get that DC + ∆Φ ≤ 2 − 2 = 0.
Chapter 3

The (h, k)-Server Problem on

Bounded Depth Trees

3.1 Introduction
In this chapter, we consider the (h, k)-server problem on special tree metrics,
in particular trees of bounded depth. Our motivation comes from the fact that
for (weighted) star graphs (trees of depth 1) we have a very good understan-
ding of the problem, while for more complex metrics like the line and arbitrary
trees, no o(h)-competitive algorithm is known. Moreover, as we mentioned in
the previous chapter, for trees of depth 1, all algorithms that are k-competitive
for k = h, attain also the optimum competitive ratio for the (h, k) setting. In
contrast, in the line we showed that the Double Coverage algorithm, which
attains the optimal competitive ratio for k = h, does not perform well in the
(h, k)-setting. Thus, it is natural to consider trees of depth 2, which are the
simplest possible extension of the weighted star, and try to get a better under-
standing on the effect of the structure of the metric space on the competitive
ratio of the (h, k)-server problem.
We first show that already in trees of small depth, all the previously known
algorithms (beyond uniform metrics), specifically the Double Coverage (DC)
algorithm and the Work Function Algorithm (WFA) have competitive ratio
Ω(h). This suggests that we need substantially new ideas in order to deal with
the (h, k)-server problem.

Theorem 3.1. The competitive ratio of DC in depth-2 trees is Ω(h), even

when k/h → ∞.

In particular, DC is unable to use the extra servers in a useful way. For

the WFA, we present the following lower bound.

29
30 3. The (h, k)-Server Problem on Bounded Depth Trees

Theorem 3.2. The competitive ratio of the WFA is at least h + 1/3 in a

depth-3 tree for k = 2h.
This lower bound can also be extended to the line metric. Note that for the
line it is known that the WFA is h-competitive for k = h [17], while our lower
bound for k = 2h is strictly larger than h. In other words, our result shows
that there exist sequences where the WFA performs strictly worse with 2h
servers than using h servers! A similar lower bound was shown in the previous
chapter for the Double Coverage algorithm. Interestingly, our lower bound
exactly matches the upper bound (h + 1)OPTh − OPTk implied by results of
[51, 17] for the WFA in the line. We describe the details in Section 3.6.
Our main result is the first o(h)-competitive algorithm for depth-d trees
with the following guarantee.
Theorem 3.3. There is an algorithm that is Od (1)-competitive on any depth-
d tree, whenever k = δh for δ > 1. More precisely, its competitive ratio is
δ 1/d d
O(d · 2d ) for δ ∈ [2d , +∞), and O(d · ( δ1/d −1
) ) for δ ∈ (1, 2d ). If δ is very
small, i.e. δ = 1 +  for 0 <  ≤ 1, the latter bound becomes O(d · (2d/)d ).
The algorithm is designed to overcome the drawbacks of DC and WFA, and
can be viewed as a more aggressive and cost-sensitive version of DC. It moves
the servers more aggressively at non-uniform speeds towards the region of the
current request, giving a higher speed to a server located in a region containing
many servers. It does not require the knowledge of h, and is simultaneously
competitive against all h strictly smaller than k.
Finally, we give an improved general lower bound. Bar-Noy and Schieber
(cf. [19, p. 175]) showed that there is no better than 2-competitive algorithm
for the (h, k)-server problem in general metrics, by constructing their lower
bound in the line metric. Our next result shows that even a 2-competitive
algorithm is not possible. In particular, we present a construction in a depth-2
HST showing that no 2.4-competitive algorithm is possible.
Theorem 3.4. There is no 2.4-competitive deterministic algorithm for trees
of depth 2, even when k/h → ∞, provided that h is larger than some constant
independent of k.
This shows that depth-2 trees are qualitatively quite different from depth-1
trees (same as weighted star graphs) which allow a ratio k/(k − h + 1). We
have not tried to optimize the constant 2.4 above, but computer experiments
suggest that the bound can be improved to about 2.88.

Preliminaries
A depth-d tree is an edge-weighted rooted tree with each leaf at depth exactly d.
In the (h, k)-server problem in a depth-d tree, the requests arrive only at leaves,
3.2. Lower Bound for Double Coverage on Depth-2 HSTs 31

and the distance between two leaves is defined as the distance in the underlying
tree. A depth-d hierarchically separated tree (HST) is a depth-d tree with the
additional property that the distances decrease geometrically away from the
root (see e.g. [15]). We will first present our algorithm for general depth-d trees
(without the HST requirement), and later show how to (easily) extend it to
arbitrary trees with bounded diameter, where requests are also allowed in the
internal nodes.
Work Function Algorithm. Consider a request sequence σ = r1 , r2 , . . . , rm .
For each i = 1, . . . , m, let wi (A) denote the optimal cost to serve requests
r1 , r2 , . . . , ri and end up in the configuration A, which is specified by the set
of locations of the servers. The function wi is called work function. The Work
Function Algorithm (WFA) decides its moves depending on the values of the
work function. Specifically, if the algorithm is in a configuration A and a
request ri ∈ / A arrives, it moves to a configuration X such that ri ∈ X and
wi (X) + d(A, X) is minimized. For more background on the WFA, see [19].

Organization
In Section 3.2, we describe the lower bound for the DC in depth-2 HSTs.
The shortcomings of the DC might help the reader to understand the motiva-
tion behind the design of our algorithm for depth-d trees, which we describe
in Section 3.3. Its extension to the bounded-diameter trees is discussed in
Section 3.4. In Section 3.5 we describe the general lower bound (Theorem 3.4)
and the lower bound for the WFA (Theorem 3.2) for depth-3 HSTs. The
extension of Theorem 3.2 to the line is discussed in Section 3.6.

3.2 Lower Bound for Double Coverage on Depth-2

HSTs
We now show a lower bound of Ω(h) on the competitive ratio of the DC algo-
rithm.
Let T be a depth-2 HST with k + 1 subtrees and edge lengths chosen as
follows. Edges from the root r to its children have length 1 − , and edges from
the leaves to their parents length  for some   1. Let Tu be a subtree rooted
at an internal node u 6= r. A branch Bu is defined as Tu together with the edge
e connecting Tu to the root. We call Bu empty, if there is no online server in
Tu nor in the interior of e. Since T contains k + 1 branches, at least one of
them is always empty.
The idea behind the lower bound is quite simple. The adversary moves all
its h servers to the leaves of an empty branch Bu , and keeps requesting those
leaves until DC brings h servers to Tu . Then, another branch has to become
32 3. The (h, k)-Server Problem on Bounded Depth Trees

r 
si
q
u

...
v s1 si−1

Figure 3.1: Move of DC during Step i. Servers s1 , . . . , si−1 are moving towards
u by distance  and si is moving down the edge (r, u) by the same distance.
While si is in the interior of (r, u), no server q from some other branch is
adjacent to v because the unique path between v and q passes through si .

empty, and the adversary moves all its servers there, starting a new phase. The
adversary can execute an arbitrary number of such phases.
The key observation is that DC is “too slow” when bringing new servers
to Tu , and incurs a cost of order Ω(h2 ) during each phase, while the adversary
only pays O(h).

Theorem 3.1. The competitive ratio of DC in depth-2 HSTs is Ω(h), even

when k/h → ∞.

Proof. We describe a phase, which can be repeated arbitrarily many times.

The adversary places all its h servers at different leaves of an empty branch Bu
and does not move until the end of the phase. At each time during the phase,
a request arrives at such a leaf, which is occupied by some offline server, but
contains no online servers. The phase ends at the moment when the hth server
of DC arrives to Tu .
Let ALG denote the cost of the DC algorithm and ADV the cost of the
adversary during the phase. Clearly, ADV = 2h in each phase: The adversary
moves its h servers to Tu and does not incur any additional cost until the end
of the phase. However, we claim that ALG = Ω(h2 ), no matter where exactly
the DC servers are located when the phase starts. To see that, let us call Step
i the part of the phase when DC has exactly i − 1 servers in Tu . Clearly, Step
1 consists of only a single request, which causes DC to bring one server to the
requested leaf. So the cost of DC for Step 1 is at least 1. To bound the cost in
the subsequent steps, we make the following observation.
Observation 3.5. At the moment when a new server s enters the subtree Tu ,
no other DC servers are located along the edge e = (r, u).
This follows from the construction of DC, which moves only servers adjacent
to the request. At the moment when s enters the edge e, no other server above
s can be inside e; see Figure 3.1.
3.3. Algorithm for Depth-d Trees 33

We now focus on Step i for 2 ≤ i ≤ h. There are already i − 1 servers in

Tu , and let si be the next one which is to arrive to Tu .
Crucially, si moves if and only if all the servers of DC in the subtree Tu
move from the leaves towards u, like in Figure 3.1: When the request arrives
at v, si moves by  and the servers inside Tu pay together (i − 1). However,
such a moment does not occur, until all servers s1 , . . . , si−1 are again at leaves,
i.e. they incur an additional cost (i − 1). To sum up, while si moves by , the
servers inside Tu incur cost 2(i − 1).
When Step i starts, the distance of si from u is at least 1 − , and therefore
si moves by distance  at least b 1− c times, before it enters Tu . So, during
Step i, DC pays at least

1− 1 − 2
 


(2(i − 1) + ) ≥ ·  2(i − 1) + 1 = (1 − 2)(2i − 1)
 

By summing over all steps i = 1, . . . , h and choosing  ≤ 1/4, we get

h h
X X h2
ALG ≥ 1 + (1 − 2)(2i − 1) ≥ (1 − 2)(2i − 1) = (1 − 2)h2 ≥
2
i=2 i=1

To conclude the proof, we note that ALG / ADV ≥ (h2 /2)/(2h) = h/4 = Ω(h)
for all phases.

3.3 Algorithm for Depth-d Trees

In this section we prove Theorem 3.3.
Recall that a depth-d tree is a rooted-tree and we allow the requests to
appear only at the leaves. However, to simplify the algorithm description, we
will allow the online servers to reside at any node or at any location on an edge
(similar to that in DC). To serve a request at a leaf v, the algorithm moves
all the adjacent servers towards v, where the speed of each server coming from
a different branch of the tree depends on the number of the online servers
“behind” it.
To describe the algorithm formally, we state the following definitions. Let
T be a depth-d tree. For a point x ∈ T (either a node or a location on some
edge), we define Tx as the subtree consisting of all points below x including x
itself, and we denote kx the number of the online servers inside Tx . If s is a
server located at a point x, we denote Ts = Tx and ks = kx . We also denote
Tx− = Tx \ {x}, and kx− the corresponding number of the algorithm’s servers in
Tx− .
34 3. The (h, k)-Server Problem on Bounded Depth Trees

1 q ...

3/6
2/6
1/6

Figure 3.2: A request at v, and Phase 2 of Algorithm 1. Note that kq− equals
6 in the visualised case. Speed is noted next to each server moving.

3.3.1 Algorithm Description

Suppose that a request arrives at a leaf v; let A be the set of algorithm’s servers
adjacent to v. The algorithm proceeds in two phases, depending on whether
there is a server along the path from v to the root r or not. We set speeds as
described in Algorithm 1 below and move the servers towards v either until the
phase ends or the set A changes. This defines the elementary moves (where
A stays unchanged). Note that if there are some servers in the path between
v and the root r, only the lowest of them belongs to A. Figure 3.2 shows the
progress of Phase 2.

Algorithm 1: Serving request at leaf v.

Phase 1: While there is no server along the path r − v
For each s ∈ A: move s at speed ks /k
Phase 2: While no server reached v; Server q ∈ A moves down along
the path r − v
For server q: move it at speed 1
For each s ∈ A \ {q}: move it at speed ks /kq−

We note two properties, the first of which follows directly from the design
of Algorithm 1.
Observation 3.6. No edge e ∈ T contains more than one server of Algorithm 1
in its interior.
Note that during both the phases, the various servers move at non-uniform
speeds depending on their respective ks . The following observations about
these speeds will be useful.
Observation
P 3.7. During Phase 1, the total speed of servers is 1. This follows
as s∈A ks = k. Analogously, during Phase P2, the total speed of servers inside
Tq− is 1, if there are any. This follows as s∈A\{q} ks = kq− .
3.3. Algorithm for Depth-d Trees 35

The intuition behind the algorithm is the following. Recall that the problem
with DC is that it moves its servers too slowly towards an active region when
requests start arriving there. In contrast, we change the speeds of the servers
adjacent to v to make the algorithm more aggressive. From each region, an
adjacent server moves at speed proportional to the number of the online servers
in that region. This way, if a region has many servers and not many requests
appear there (we call such regions excessive), servers move quickly from there
to a more active region. Moreover, in Phase 2, server q is viewed as a helper
coming to aid the servers inside Tq− . The second main idea is to keep the total
speed of the helper proportional to the total speed of the servers inside Tq− .
This prevents the algorithm from becoming overly aggressive and keeps the
cost of the moving helpers comparable to the cost incurred within Tq− .

3.3.2 Analysis
We will analyze the algorithm based on a suitable potential function Φ(t). Let
ALG(t) and OPT(t) denote the cost of the algorithm and of the adversary
respectively, for serving the request at time t. Let ∆t Φ = Φ(t) − Φ(t − 1)
denote the change of the potential at time t. We will ensure that Φ is non-
negative and bounded from above by a function of h, k, d, and length of the
longest edge in T . Therefore, to show R-competitiveness, it suffices to show
that the following holds at each time t: ALG(t) + ∆t Φ ≤ R · OPT(t).
To show this, we split the analysis into two parts: First, we let the adversary
move a server (if necessary) to serve the request. Then we consider the move
of the algorithm. Let ∆OP t
T Φ and ∆ALG Φ denote the changes in Φ due to
t
the move of the adversary and the algorithm respectively. Clearly, ∆t Φ =
∆OP
t
T Φ + ∆ALG Φ, and thus it suffices to show the following two inequalities:
t

∆OP
t
T
Φ ≤ R · OP T (t) (3.1)
ALG(t) + ∆ALG
t Φ≤0 (3.2)

Potential function
Before we define the potential, we need to formalize the notion of excess and
deficiency in the subtrees of T . Let d(a, b) denote the distance of points a
and b. For e = P (u, v) ∈ T , where v is the node closer to the root, we define
1
ke := ku + d(u,v) s∈e d(s, v). Note that this is the number of online servers in
Tu , plus the possible single server in e counted fractionally, proportionally to
its position along e. For an edge e, let `(e) denote its level with the convention
that the edges from leaf to their parents have level 1, and the edges from root
to its children have level d. For ` = 1, . . . , d, let β` be some geometrically
increasing constants that will be defined later. For any point x ∈ T , similarly
36 3. The (h, k)-Server Problem on Bounded Depth Trees

to kx and kx− , we denote hx and h−

x the number of servers of the adversary in
Tx and Tx− respectively. For and edge e we define the excess Ee of e and the
deficiency De of e as follows

Ee = max{ke − bβ`(e) · hu c, 0} · d(u, v) De = max{bβ`(e) · hu c − ke , 0} · d(u, v).

Note that these compare ke to hu with respect to the excess threshold β`(e) .
We call an edge excessive, if Ee > 0, otherwise we call it deficient. Let us state
a few basic properties of these two terms.

Observation 3.8. Let e be an edge containing an algorithm’s server s in its

interior. If e is excessive, it cannot become deficient unless s moves upwards
completely outside of the interior of e. Similarly, if e is deficient, it cannot
become excessive unless s leaves interior of e completely.

Note that no other server can pass through e while s still resides there and the
contribution of s to ke is a nonzero value strictly smaller than 1, while bβ` hu c
is an integer.

Observation 3.9. Let e be an edge and s be an algorithm’s server in its

interior moving by a distance x. Then either De or Ee changes exactly by x.

This is because ke changes by x/d(u, v), and therefore the change of De (resp. Ee )
is x.

Observation 3.10. If an adversary server passes through the edge e, change

in De (resp. Ee ) will be at most dβ` e · d(u, v).

To see this, note that bβ`(e) hu c ≤ bβ`(e) (hu − 1)c + dβ`(e) e.

We now fix the excess thresholds. We first define β depending on δ = k/h
as,
β = 2 if δ ≥ 2d , and β = δ 1/d for δ ≤ 2d .
β
For convenience in the calculations, we denote γ := β−1 . Note that, for all
possible δ > 1, our choices satisfy 1 < β ≤ 2, γ ≥ 2 and

β ≤ δ 1/d . (3.3)

For each ` = 1, . . . , d, we define the excess threshold for all edges in the level `
as β` := β `−1 .
Now, we can define the potential. Let
X 
D E
Φ := α`(e) De + α`(e) Ee ,
e∈T
3.3. Algorithm for Depth-d Trees 37

where the coefficients α`D and α`E are as follows:

α`D := 2` − 1 for ` = 1, . . . , d
1 D
αdE := γ(1 + α )
β d
d−1  
X 1
α`E := γ i−`+1
2 + αiD + γ d−` αdE for ` = 1, . . . , d − 1.
β
i=`

Note that α`D > α`−1 D and αE < αE

` `−1 for all 1 < ` ≤ d. The latter follows as
the multipliers γ i−`+1 and γ d−` decrease with increasing ` and moreover the
summation in the first term of α`E has fewer terms as ` increases.
To prove the desired competitive ratio for Algorithm 1, the idea will be to
show that the good moves (when a server enters a region with deficiency, or
leaves a region with excess) contribute more than the bad moves (when a server
enters a region with excess, or leaves a region that is already deficient).
As the dynamics of the servers can be decomposed into elementary moves,
it suffices to only analyze these. We will assume that no servers of A are located
at a node. This is without loss of generality, as only the moving servers can
cause a change in the potential, and each server appears at a node just for
an infinitesimal moment during its motion. Note that this assumption implies
that each edge e containing a server s ∈ A is either excessive or deficient, i.e.
either Ee > 0 or De > 0.
The following two lemmas give some properties of the deficient and excessive
subtrees, which will be used later in the proof of Theorem 3.3.

Lemma 3.11 (Excess in Phase 1). Consider a moment during Phase 1 and
assume that no server of A resides at a node. For the set E = {s ∈ A | s ∈
e, Ee > 0} of servers which are located in excessive edges, and for D = A \ E,
the following holds.
X 1 X 1
ks ≤ k and ks ≥ k.
β γ
s∈D s∈E

Proof. During Phase 1, each

P server P of the algorithm resides in Ts for some
s ∈ E ∪ D; therefore k = s∈E ks + s∈D ks . For each s ∈ D, let `(s) be the
level of the edge e containing s. We have that ks ≤ bβ`(s) · hs c, otherwise Ee
would be positive. Therefore we have
X X X k k 1
ks ≤ bβ`(s) hs c ≤ βd · hs ≤ βd · h = β d−1 ≤ β d−1 d = k,
δ β β
s∈D s∈D s∈D

where the last inequality comes from (3.3).

38 3. The (h, k)-Server Problem on Bounded Depth Trees

To prove the second inequality, observe that

X X 1 1 1
ks = k − ks ≥ k − k = (1 − )k = k.
β β γ
s∈E s∈D

Lemma 3.12 (Excess in Phase 2). Consider a moment during Phase 2 and
assume that no server of A resides at a node. Let ` be the level of the edge
containing q and A0 = A \ {q}. For the set E = {s ∈ A0 | s ∈ e, Ee > 0} of
servers which are located in excessive edges, and for D = A0 \ E, the following
holds. If kq− ≥ bβ` h−
q c, then we have

X 1 − X 1 −
ks ≤ k and ks ≥ k .
β q γ q
s∈D s∈E

Proof. The proof is quite similar to the proof of Lemma 3.11. Instead of using
the fact that δ ≥ β d = β · β d−1 = β · βd , we now crucially use the fact that
β` = β · β`−1 . However, now we have to be more careful with the counting of
the servers of the adversary.
For each s ∈ D, let `(s) be the level of the edge e containing s. Similarly
to the proof of Lemma 3.11, we have ks ≤ bβ`(s) · hs c ≤ β`−1 · hs for each
server s ∈ D, since `(s) ≤ ` − 1. Recall that we assume that the adversary has
already served the request. Let a be the server of the adversary located at the
requested point. Since no online servers reside in the path between q and the
requested point,
P a does not belong to Ts for any s ∈ D ∪ E. Therefore we have
− − 1. We get that
P
h
s∈D s ≤ h
s∈(D∪E) s ≤ hq
X X
ks ≤ β`−1 · hs ≤ β`−1 (h−
q − 1). (3.4)
s∈D s∈D

To finish the proof of the first inequality, observe that our assumption that
kq− ≥ bβ` h−
q c implies

kq− + 1
kq− ≥ bβ` h− − − −
q c ⇒ β` hq ≤ kq + 1 ⇔ hq ≤ .
β`
Therefore, from (3.4) we have
X kq− + 1 β`−1 − 1 1
ks ≤ β`−1 (h−
q − 1) ≤ β`−1 ( − 1) = kq + − β`−1 ≤ kq− .
β` β` β β
s∈D

1 1 −
P
P For the second inequality, note that γ = (1 − β ). Since kq = s∈D ks +
s∈E ks , we have
X 1 1
ks ≥ kq− − kq− = kq− .
β γ
s∈E
3.3. Algorithm for Depth-d Trees 39

Proof of Theorem 3.3

We now show the main technical result, which directly implies Theorem 3.3.

Theorem 3.13. The competitive ratio of Algorithm 1 in depth-d trees is O(d ·

γ d ).

This implies Theorem 3.3 as follows. If δ ≥ 2d , we have β = 2 and γ = 2,

and we get the competitive ratio O(d·2d ). For 1 < δ < 2d , we have β = δ 1/d and
δ 1/d d
therefore the competitive ratio is O(d · ( δ1/d −1
) ). In particular, if δ = (1 + )

for some 0 <  ≤ 1, we have β = (1 + )1/d ≥ 1 + 2d . This implies that
β β
γ = β−1 ≤ /(2d) = β2d
 . Using (3.3), we get that

2d d 2d 2d
γd ≤ βd · ( ) ≤ δ · ( )d = O(( )d ).
  

Thus, we get the ratio O(d · ( 2d d

 ) ).
We now prove Theorem 3.13.

Proof of Theorem 3.13. As Φ is non-negative and bounded from above by a

function of h, k, d, and the length of the longest edge in T , it suffices to show
the inequalities (3.1) and (3.2).
We start with (3.1) which is straightforward. By Observation 3.10, the
move of a single adversary’s server through an edge e of length xe changes De
or Ee in the potential by at most dβ`(e) exe . As the adversary incurs cost xe
during this move, we need to show the following inequalities:

dβ` exe · α`D ≤ R · xe for all 1 ≤ ` ≤ d

dβ` exe · α`E ≤ R · xe for all 1 ≤ ` ≤ d.

As we show in Lemma 3.16 below, dβ` eα`D and dβ` eα`E are of order O(d · γ d ).
Therefore, setting R = Θ(d · γ d ) will satisfy (3.1).
We now consider (3.2) which is much more challenging to show. Let us
denote AE the set of edges containing some server from A in their interior. We
call an elementary step a part of the motion of the algorithm during which A
and AE remain unchanged, and all the servers of A are located in the interior
of the edges of T . Lemmas 3.14 and 3.15 below show that (3.2) holds during
an elementary step, and the theorem would follow by summing (3.2) over all
the elementary steps.

Lemma 3.14. During an elementary step in Phase 1 of Algorithm 1, the

inequality (3.2) holds.
40 3. The (h, k)-Server Problem on Bounded Depth Trees

Proof. Without loss of generality, let us assume that the elementary step lasted
exactly 1 unit of time. This makes the distance traveled by each server equals
to its speed, and makes calculations cleaner.
Let ALG denote the cost incurred by the algorithm during this step. Note
that ALG = 1, since by Observation 3.7, the total speed of the servers in A, is
1.
To estimate the change of the potential ∆Φ, we decompose A into two sets,
called D and E. D is the set of the servers of A residing in deficient edges,
and E are the servers residing in excessive edges. Next, we evaluate ∆Φ due
to the movement of the servers from each class separately.
The movement of servers of E is good, i.e. decreases the excess in their
edges, while the movement of servers of D increases the deficiency. By taking
the largest possible αD (which is αdD ) and the smallest possible αE (which is
αdE ) coefficient in the estimation, we can bound the change of the potential due
to the move of the servers of A as
X ks X ks 1 1
∆Φ ≤ αdD − αdE ≤ αdD − αdE ,
k k β γ
s∈D s∈E

where the last inequality holds due to the Lemma 3.11. We get that
1 D 1 E 1 1 1
ALG +∆Φ ≤ 1 + αd − αd = 1 + αdD − · γ(1 + αdD ) = 0.
β γ β γ β
Lemma 3.15. During an elementary step in Phase 2 of Algorithm 1, the
inequality (3.2) holds.
Proof. Similarly to the proof of the preceding lemma, we denote by ALG the
cost incurred by the algorithm and we assume (without loss of generality) that
the duration of the elementary step is exactly 1 time unit, so that the speed of
each server equals the distance it travels. As the speed of the server q is 1, it
also moves by distance 1. Moreover, by Observation 3.7, the servers in Tq− (if
any) move in total by s∈A\{q} kk−s = 1, and therefore ALG ≤ 2. We denote by
P
q
` the level of the edge containing q. To estimate the change of the potential,
we consider two cases.
1. When kq− ≥ bβ` h− q c. Here the movement of q increases the excess in the
edge containing q. Let us denote E (resp. D) the servers of A\{q} residing
in the excessive (resp. deficient) edges. By taking the largest possible αD
D ) and the smallest possible αE (which is αE ) coefficient
(which is α`−1 `−1
in the estimation, we can upper bound the change of the potential due
to the move of the servers in Tq− as,
X ks X ks 1 D 1 E
D E
α`−1 − − α`−1 − ≤ β α`−1 − γ α`−1 ,
k
s∈D q
k
s∈E q
3.3. Algorithm for Depth-d Trees 41

where the above inequality holds due to the Lemma 3.12. As the mo-
vement of q itself causes an increase of Φ by α`E , we have
1 D 1 E
ALG + ∆Φ ≤ 2 + α`−1 − α`−1 + α`E .
β γ
 
To see that this is non-positive, recall that α`E = d−1 i−`+1 2 + 1 αD +
P
i=` γ β i
γ d−` αdE . Therefore
d−1
1 E 1 X i−`+2 1
1
α`−1 = γ 2 + αiD + γ d−`+1 αdE
γ γ β γ
i=`−1
d−1
1 D
X i−`+1 1
2 + αiD + γ d−` αdE


= 2+ α`−1 + γ
β β
i=`
1 D
= 2 + α`−1 + α`E .
β

2. When kq− < bβ` h−

q c. This case is much simpler. All the movement inside
−
of Tq might contribute to the increase of deficiency at level at most
` − 1. On the other hand, q then causes a decrease of deficiency at level
` and we have ALG +∆Φ ≤ 2 + α`−1 D − αD . This is less or equal to 0, as
`
D +2
α`D ≥ α`−1 .
Lemma 3.16. For each 1 ≤ ` ≤ d, both dβ` eα`D and dβ` eα`E are of order
O(d · γ d ).
Proof. We have defined α`D = 2` − 1, and therefore
dβ` eα`D ≤ 2 · β ` (2` − 1) ≤ 2 · β d (2d − 1) = O(d · γ d ),
since we have chosen 1 < β ≤ 2 and γ ≥ 2 for any possible δ.
Now we focus on α`E . Note that αdE = γ(1 + β1 αdD ), which is O(d · γ), as
β > 1 and αdD = O(d). For α`E , we have
d−1   d−1
X 1 D 1 D X i−`+1
α`E = γ i−`+1 d−` E
2 + αi + γ αd ≤ (2 + αd−1 ) γ + γ d−` αdE =
β β
i=` i=`
d−`
1 D X 1 D γ · (γ d−` − 1)
= (2 + α ) γ j + γ d−` αdE = (2 + α ) + γ d−` αdE
β d−1 β d−1 γ−1
j=1
1 D
≤ β(2 + αd−1 )γ d−` + γ d−` αdE = γ d−` (2β + 2d − 3 + αdE ) = O(γ d−`+1 · d),
β
γ
where we used that γ−1 = β, 1 < β ≤ 2 and αdE = O(γ · d). Therefore, as
β` ≤ γ `−1 , we have dβ` eα`E = O(γ d d), and this concludes the proof.
42 3. The (h, k)-Server Problem on Bounded Depth Trees

3.4 Algorithm for Bounded-Diameter Trees

Since Algorithm 1 works for depth-d trees with arbitrary edge lengths, we can
embed any diameter-d tree into a depth-d tree with a very small distortion by
adding fake paths of short edges to all nodes.
More precisely, let T be a tree of diameter d with arbitrary edge lengths,
and let α be the length of the shortest edge of T (for any finite T such α exists).
We fix  > 0 a small constant. We create an embedding T 0 of T as follows. We
choose the root r arbitrarily, and to each node v ∈ T such that the path from
r to v contains ` edges, we attach a path containing d − ` edges of total length
α/2. The leaf at the end of this path we denote v 0 . We run Algorithm 1
in T 0 and each request at v ∈ T we translate to v 0 ∈ T 0 . We maintain the
correspondence between the servers in T and the servers in T 0 , and the same
server which is finally moved to v 0 by Algorithm 1, we also use to serve the
request v ∈ T .
For the optimal solutions on T and T 0 we have (1 + ) OPT(T ) ≥ OPT(T 0 ),
since any feasible solution in T we can be converted to a solution in T 0 with
cost at most (1 + ) times higher. By Theorem 3.13, we know that the cost of
Algorithm 1 in T 0 is at most R · OPT(T 0 ), for R = Θ(d · γ d+1 ), and therefore
we have ALG(T 0 ) ≤ (1 + )R · OPT(T ).

3.5 Lower Bounds

In this section we prove Theorems 3.4 and 3.2. We first show a general lower
bound on the competitive ratio of any algorithm for depth-2 HSTs. Then we
give lower bound on the competitive ratio of WFA. Similarly to the previous
section, given a tree T and a point x ∈ T (either a node or a location on some
edge), we define Tx as the subtree consisting of all points below x including x
itself. If u is a parent of a leaf, we call Tu an elementary subtree.

3.5.1 General Lower Bound for Depth-2 HSTs

We now give a lower bound on the competitive ratio of any deterministic online
algorithm on depth-2 HSTs. In particular, we show that for sufficiently large
h, any deterministic online algorithm has competitive ratio at least 2.4.
The metric space is a depth-2 HST T with the following properties: T
contains at least k + 1 elementary subtrees and each one of them has at least h
leaves. To ease our calculations, we assume that edges of the lower level have
length   1 and edges of the upper level have length 1 − . So the distance
between leaves of different elementary subtrees is 2.
Theorem 3.4 (restated). For sufficiently large h, even when k/h → ∞, there
is no 2.4-competitive deterministic online algorithm, even for depth-2 HSTs.
3.5. Lower Bounds 43

Proof. Without loss of generality both the online and offline algorithms are
“lazy”, i.e. they move a server only for serving a request (this is a folklore
k-server property, see e.g. [19]). Since requests only appear at leaves of T , all
the offline and online servers are always located at the leaves. We say that a
server is inside an elementary subtree Tu , if it is located at some leaf of Tu . If
there are no online servers at the leaves of Tu , we say that Tu is empty. Observe
that at any given time there exists at least one empty elementary subtree.
Let A be an online algorithm. The adversarial strategy consists of arbitra-
rily many iterations of a phase. During a phase, some offline servers are moved
to an empty elementary subtree Tu and requests are made there until the cost
incurred by A is sufficiently large. At this point the phase ends and a new
phase may start in another empty subtree. Let ALG and ADV denote the cost
of A and the adversary respectively during a phase. We will ensure that for
all phases ALG ≥ 2.4 · ADV. This implies the lower bound on the competitive
ratio of A.
We describe a phase of the adversarial strategy. The adversary moves some
` ≤ h servers to the empty elementary subtree Tu and makes requests at leaves
of Tu until A brings m servers there. In particular, each request appears at a
leaf of Tu that is not occupied by a server of A. We denote by s(i) the cost that
A has to incur for serving requests inside Tu until it moves its ith server there
(this does not include the cost of moving the server from outside Tu ). Clearly,
s(1) = 0 and s(i) ≤ s(i + 1) for all i > 0. The choice of ` and m depends on
the values s(i) for 2 ≤ i ≤ h. We will now show that for any values of s(i)’s,
the adversary can choose ` and m such that ALG ≥ 2.4 · ADV.
First, if there exists an i such that s(i) ≥ 3i, we set ` = m = i. Intuitively,
the algorithm is too slow in bringing its servers to Tu in this case. Both A
and the adversary incur a cost of 2i to move i servers to Tu . However, A pays
a cost of s(i) for serving requests inside Tu , while the adversary can serve all
those requests at zero cost (all requests can be located at leaves occupied by
offline servers). Overall, the cost of A is 2i + s(i) ≥ 5i, while the offline cost is
2i. Thus we get that ALG ≥ 2.5 · ADV.
Similarly, if s(i) ≤ (10i − 24)/7 for some i, we choose ` = 1 and m = i.
Roughly speaking, in that case the algorithm is too “aggressive” in bringing
its first i servers, thus incurring a large movement cost. Here, the adversary
only moves one server to Tu . Each request is issued at an empty leaf of Tu .
Therefore A pays for each request in Tu and the same holds for the single server
of the adversary. So, ALG = 2i + s(i) and ADV = 2 + s(i). By our assumption
on s(i), this gives
ALG −2.4 · ADV = 2i + s(i) − 4.8 − 2.4 · s(i) = 2i − 4.8 − 1.4 · s(i) ≥ 0.
We can thus restrict our attention to the case that s(i) ∈ ( 10i−24
7 , 3i), for
all 2 ≤ i ≤ h. Now we want to upper bound the offline cost, for 1 < ` < h and
44 3. The (h, k)-Server Problem on Bounded Depth Trees

m = h. Clearly, the offline movement cost is 2`, and for the time that A has
less than ` servers in Tu , the offline cost is zero. It remains to count the offline
cost during the time that A has at least ` servers inside Tu .
For the part of the request sequence when A has ` ≤ j < h servers in Tu ,
it incurs a cost s(j + 1) − s(j). Since the problem restricted to an elementary
subtree is equivalent to the paging problem, using the lower bound result of
[66] for paging1 , we get that the adversary incurs a cost of at most (s(j + 1) −
s(j)) · j−`+1
j
h−`
+ 2j ≤ (s(j + 1) − s(j)) · h−1 + 2j. Also, there are h − ` requests
where A brings new servers. Clearly, those requests cost to the adversary at
most (h − `)2. Thus the cost of the adversary inside Tu is at most
h−1 
X h−` 
(s(j + 1) − s(j)) · + 2j + (h − `)2
h−1
j=`
h−1
h−`
X
= s(h) − s(`) + 2 j + (h − `)2.
h−1
j=`

For any value of h, we can take  small enough, such that the terms involving
 tend to zero. Thus the upper bound on the offline cost is arbitrarily close to
h−`
2` + (s(h) − s(`)) · h−1 , where the first term is the cost of moving ` servers to
Tu . Let us denote c = s(h)/h. Note that assuming h is large enough, c ∈ (1, 3).
We get that

ALG 2h + s(h) 2h + ch
≥ h−`
≥ (3.5)
ADV 2` + (s(h) − s(`)) · h−1 2` + (ch − 10`−24
7 )· h−`
h−1
2h + ch
= (3.6)
2` + h · (c − 10`−24 h−`
7h ) · h−1

We now show that for every value of c ∈ (1, 3), there is an ` = bβhc, where
β ∈ (0, 1) is a constant depending on c, such that this ratio is at least 2.4.
First, as h is large enough, (3.6) is arbitrarily close to

2h + ch 2h + ch
=

2` + h · (c − 10`/7h) · (1 − `/h) 2` + h c − c`/h − 10`/(7h) + 10`2 /(7h2 )

2h + ch
≥

2βh + h c − c(βh − 1)/h − 10(βh − 1)/(7h) + 10β 2 h2 /(7h2 )
1
Sleator and Tarjan [66] show that an adversary with h servers can create a request
sequence against an online algorithm with k servers such that the cost of the adversary is at
most k−h+1
k
ALG +(k − h + 1) · D, where D is the distance between two leaves.
3.5. Lower Bounds 45

2+c 2+c
→
2β + c − cβ + c/h − 10β/7 + 10/(7h) + 10β 2 /7 (10/7) · β 2 + (4/7 − c)β + c

We choose β := (c − 4/7)/(20/7). Note that, as c ∈ (1, 3), we have that

β < 1 and hence ` < h. The expression above then evaluates to (2+c)/(c−(c−
√
4 2 40
7 ) / 7 ). By standard calculus, this expression is minimized at c = (2 221 −
14)/7 where it attains a value higher than 2.419.

3.5.2 Lower Bound for WFA on Depth-3 HSTs

We give an Ω(h) lower bound on the competitive ratio of the Work Function
Algorithm (WFA) in the (h, k)-setting. More precisely, we show a lower bound
of h + 1/3 for k = 2h. We first present the lower bound for a depth-3 HST. In
Section 3.6 we show how the construction can be adapted to work for the line.
We also show that this exactly matches the upper bound of (h + 1) · OPTh −
OPTk implied by results of [51, 17] for the line.
The basic idea behind the lower bound is to trick the WFA to use only
h servers for servicing requests in an “active region” for a long time before it
moves its extra available online servers. Moreover, we make sure that during
the time the WFA uses h servers in that region, it incurs an Ω(h) times higher
cost than the adversary. Finally, when the WFA brings its extra servers, the
adversary moves all its servers to some different region and starts making
requests there. So eventually, WFA is unable to use its additional servers
in a useful way to improve its performance.
Theorem 3.2 (restated) The competitive ratio of the WFA in a depth-3 HST
for k = 2h is at least h + 1/3.

Proof. Let T be a depth-3 HST. We assume that the lengths of the edges in a
−0 0 0
root-to-leaf path are 1−
2 , 2 , 2 , for     1. So the diameter of T is 1 and
the diameter of depth-2 subtrees is . We also assume that N = 1 is integer
such that N  3h 2 . Let L and R be two subtrees of depth 2. Inside each
one of them, we focus on 2 elementary subtrees L1 , L2 and R1 , R2 respectively
(see figure 3.3), each one containing exactly h leaves. All requests appear at
leaves of those elementary subtrees. Initially all servers are at leaves of L.
Thus, both the WFA and the adversary always have their servers at leaves.
This way, we say that some servers of the WFA (or the adversary) are inside
a subtree, meaning that they are located at some leaves of that subtree.
The adversarial strategy consists of arbitrary many iterations of a phase.
At the beginning of the phase, all online and offline servers are in the same
subtree, either L or R. At the end of the phase, all servers have moved to
the other subtree (R or L resp.), so a new phase may start. Before describing
46 3. The (h, k)-Server Problem on Bounded Depth Trees

L R

L1 L2 R1 R2
· · ·· · · · · ·· · · · · ·· · · · · ·· · ·

Figure 3.3: The tree where the lower bound for WFA is applied: All requests
arrive at leaves of L1 , L2 , R1 and R2 .

the phase, we give the basic strategy, which is repeated many times. For any
elementary subtree T with leaves t1 , . . . , th , any 1 ≤ ` ≤ h and any c > 0, we
define strategy S(T, `, c).
Strategy S(T, `, c):

1. While the WFA has i < ` servers in T : Request points t1 , . . . , t` in an

adversarial way (i.e each time request a point where the WFA does not
have a server).

2. If ` ≥ 2 and the WFA has i ≥ ` servers in T , then: While optimal cost to

serve all requests using ` − 1 servers (starting at t1 , . . . , t`−1 ) is smaller
than c, request points t1 , . . . , t` in a round-robin way.

Note that the 2nd part might not be executed at all, depending on the values
of ` and c.
We now describe a left-to-right phase, i.e., a phase which starts with all
servers at L and ends with all servers at R. A right-to-left phase is completely
symmetric, i.e., we replace R by L and Ri by Li . Recall that N = 1 .

Left-to-right phase:
Step 1: For ` = 1 to h: Apply strategy S(R1 , `, 2)
Step 2: For i = 1 to N + 1:
For ` = 1 to h: Apply strategy S(R2 , `, 2)
For ` = 1 to h: Apply strategy S(R1 , `, 2)

Intuitively, the WFA starts with no server at R and at the end of Step 1,
it has h servers there (more precisely, in R1 ). During Step 2, the WFA moves
all its servers to R, as we show later.
Let ALG and ADV be the online and offline cost respectively. We now state
two basic lemmas for evaluating ALG and ADV during each step. Proofs of
3.5. Lower Bounds 47

those lemmas, require a characterization of work function values, which comes

later on. Here we just give the intuition behind the proofs.
Lemma 3.17. During Step 1, ALG ≥ h2 − 0 · (h − 1)h and ADV = h.
Intuitively, we will exploit the fact that the WFA moves its servers too
slowly towards R. In particular, we show (Lemma 3.37) that whenever the
WFA has i < h servers in R, it incurs a cost of at least (2 − 20 ) · i inside R
before it moves its (i + 1)th server there. This way we get that the cost of the
Ph−1
algorithm is at least h + i=1 (2 − 20 ) · i = h2 − 0 · (h − 1)h. On the other
hand, the adversary moves its h servers by distance 1 (from L to R1 ) and then
it serves all requests at zero cost.
0
Lemma 3.18. During Step 2, ALG ≥ 2h2 + h − 3h3 − 2  · (h − 1) · h and
ADV = (2 + 2)h.
Roughly speaking, to prove this lemma we make sure that for almost the
whole Step 2, the WFA has h servers in R and they incur a cost h times higher
than the adversary. The additional servers move to R almost at the end of the
phase. The cost of the adversary is easy to calculate. There are N +1 = 1/+1
iterations, where in each one of them the adversary moves its h servers from
R1 to R2 and then back to R1 , incurring a cost of 2 · h.
The theorem follows from lemmata 3.17 and 3.18. Summing up for the
whole phase, the offline cost is (3 + 2) · h and the online cost is at least
0
3h2 + h − 3h3 −  2(h − 1)h − 0 (h − 1)h. We get that

0
ALG 3h2 + h − 3h3 −  2(h − 1)h − 0 (h − 1)h 3h2 + h 1
≥ → =h+
ADV (3 + 2)h 3h 3

Work Function values

We now give a detailed characterization of how the work function evolves du-
ring left-to-right phases. For right-to-left phases the structure is completely
symmetric.
Basic Properties: We state some standard properties of work functions that
we use extensively in the rest of this section. Proofs of those properties can be
found e.g. in [19]. First, for any two configurations X, Y at distance d(X, Y )
the work function w satisfies,

w(X) ≤ w(Y ) + d(X, Y ).

Also, let w and w0 be the work function before and after a request r respectively.
For a configuration X such that r ∈ X, we have that w0 (X) = w(X). Last,
48 3. The (h, k)-Server Problem on Bounded Depth Trees

let C and C 0 be the configurations of the WFA before and after serving r
respectively. The work function w0 satisfies w0 (C) − w0 (C 0 ) = d(C, C 0 ).
Notation: Let (Li , Rk−i ) denote a configuration which has i servers at L and
(k − i) servers at R. Let w(Li , Rk−i ) be the minimum work function value of a
configuration (Li , Rk−i ). If we need to make precise how many servers are in
each elementary subtree, we denote by (Li , r1 , r2 ) a configuration which has i
servers at L, r1 servers at R1 and r2 servers at R2 . Same as before, w(Li , r1 , r2 )
denotes the minimum work function value of those configurations.
Definition: For two configurations X and Y , we say that X supports Y , if
w(Y ) = w(X) + d(X, Y ). The set of configurations that are not supported by
any other configuration is called the support of work function w. The following
observation will be useful later in our proofs.
Initialization: For convenience we assume that at the beginning of the phase
the minimum work function value of a configuration is zero. Note that this is
without loss of generality: If m = minX w(X) when the phase starts, we just
subtract m from the work function values of all configurations. We require the
invariant that at the beginning of the phase, for 0 ≤ i ≤ k :

w(Lk−i , Ri ) = i.

This is clearly true for the beginning of the first phase, as all servers are
initially at L. We are going to make sure, that the symmetric condition (i.e.
w(Li , Rk−i ) = m + i) holds at the end of the phase, so a right-to-left phase
may start.
We now state two auxiliary lemmata which would be helpful later.

Lemma 3.19. Consider a left-to-right phase. At any time after the end of stra-
tegy S(R1 , `, 2), for 1 ≤ ` ≤ h, we have that w(Lk−`+1 , R`−1 ) = w(Lk−` , R` )+1.

At a high-level, the reason that this lemma holds is that any schedule S
that uses no more than ` − 1 servers in R1 , incurs a cost of at least 2 during
the execution of S(R1 , `, 2). Thus, by moving an `th server to R1 (cost 1), and
serving all requests of S(R1 , `, 2) at zero cost, we obtain a schedule which is
cheaper than S by at least 1. The formal proof is deferred to the end of this
section.

Lemma 3.20. Consider a left-to-right phase. At any time after the end of
strategy S(R1 , `, 2), for 1 ≤ ` ≤ h, we have that w(Lk−i , Ri ) = w(Lk−` , R` ) +
(` − i) for any 0 < i < `.

Proof. We use backwards induction on i. Note that the base case i = ` − 1 is

true due to Lemma 3.19. Let t be any time after the end of strategy S(R1 , `, 2)
with work function w.
3.5. Lower Bounds 49

Induction Step: Assume that the lemma is true for some i < `. We show
that the lemma holds for i − 1. Clearly, time t is after the end of S(R1 , i, 2).
From Lemma 3.19 we have that

w(Lk−i+1 , Ri−1 ) = w(Lk−i , Ri ) + 1. (3.7)

From the inductive hypothesis we have that

w(Lk−i , Ri ) = w(Lk−` , R` ) + (` − i). (3.8)

By (3.7), (3.8) we get that

w(Lk−i+1 , Ri−1 ) = w(Lk−i , Ri ) + 1 = w(Lk−` , R` ) + ` − (i − 1).

First Step: We now focus on the first step of the phase. Using the two
lemmata above, we can characterize the structure of the work function at the
end of the execution of S(R1 , `, 2), for 1 ≤ ` ≤ h.

Lemma 3.21. Consider a left-to-right phase. When strategy S(R1 , `, 2) ends,

for any 1 ≤ ` ≤ h, the following two things hold:

1. For all 0 ≤ i < `, w(Lk−i , Ri ) = w(Lk−` , R` ) + (` − i)

2. For all ` < i ≤ k, w(Lk−i , Ri ) = w(Lk−` , R` ) + (i − `)

In other words, having ` servers in R is the lowest state, and all other states
are tight with respect to it.

Proof. For i < `, the lemma follows from Lemma 3.20. We focus on i ≥ `:
Until the end of S(R1 , `, 2) there are ` ≤ i points in R requested, so w(Lk−i , Ri )
does not change. Since at the beginning w(Lk−i , Ri ) = i, we have that for all
i≥`+1
w(Lk−i , Ri ) − w(Lk−` , R` ) = i − `.

This characterization of work function values is sufficient to give us the

lower bound on the cost of the WFA during Step 1. The reader might prefer
to move to Lemma 3.37 which estimates the cost of the WFA during the time
interval that it has i < h servers in R, and implies Lemma 3.17.
Second step: By lemma 3.21, at the beginning of the second step, the work
function values satisfy:

w(L2h−i , Ri ) = w(Lh , Rh ) + (h − i), for 0 ≤ i < h, (3.9)

w(L2h−i , Ri ) = w(Lh , Rh ) + (i − h), for h < i ≤ 2h, (3.10)

We note that (3.9) holds for the entire second step, due to Lemma 3.20.
50 3. The (h, k)-Server Problem on Bounded Depth Trees

Characterizing the structure of the work function during second step is

more complicated. Note that Step 2 consists of N + 1 iterations, where in
each iteration strategies S(R2 , `, 2) and S(R1 , `, 2) are applied. The following
auxiliary lemma will be helpful in our arguments about the evolution of the
work function during step 2.

Lemma 3.22. For any 0 ≤ i < h, the optimal schedule to serve c consecutive
iterations of Step 2 using h + i servers in R, starting from a configuration
(Lh−i , h, i) and ending up in a configuration (Lh−i , h − i0 , i + i0 ), for 0 ≤ i0 ≤
h − i, has cost c · 2(h − i) +  · i0 .

Proof. Consider a schedule S serving c consecutive iterations of Step 2 using

h + i servers in R, starting from a configuration (Lh−i , h, i). For j = 1, . . . , c,
let (Lh−i , h − aj−1 , i + aj−1 ) be the configuration of S at the beginning of jth
iteration. Let also (Lh−i , i + bj , h − bj ) be the configuration of S at the end of
the execution of S(R2 , h, 2) during jth iteration. At the end of jth iteration,
S is in configuration (Lh−i , h − aj , i + aj ) and the (j + 1)th iteration starts.
Note that 0 ≤ aj , bj ≤ h − i, for all 1 ≤ j ≤ c. Clearly, a0 = 0, since we assume
that S starts at a configuration (Lh−i , h, i).
We now calculate the minimum cost of S depending on the values of aj
and bj . Consider the jth iteration. During executions of S(R2 , `, 2) there are
h − bj − (i + aj−1 )) servers that move from R1 to R2 , incurring a movement
cost of (h − bj − i − aj−1 ). The cost of serving requests in R2 is at least 2 · bj ,
which is incurred during executions of S(R2 , `, 2) for h−bj < ` ≤ h. Similarly,
the movement cost for moving servers from R2 to R1 is (h − aj − i − bj ) and
the cost incurred inside R1 is at least 2aj . We get that the total cost of S is
at least
c
X c
X
· (h − bj − i − aj−1 ) + (h − aj − i − bj ) + 2aj + 2bj =  · 2h − 2i + aj − aj−1
j=1 j=1

c
X
= c · 2(h − i) +  · aj − aj−1 = c · 2(h − i) +  · ac .
j=1

By setting i0 = ac , the lemma follows.

We get the following corollary.

Corollary 3.23. The optimal schedule to serve c consecutive iterations of Step

2 using h + i servers in R, starting from a configuration (Lh−i , h, i) has cost
c · 2(h − i), and it ends up in a configuration (Lh−i , h, i).

The following definition is going to be helpful for characterizing the changes

in the work function during various iterations of Step 2.
3.5. Lower Bounds 51

Definition 3.24. An iteration of Step 2 is called good if the following condi-

tions hold:

(i) During the whole iteration, for all 0 ≤ i < h and 0 < j ≤ h − i, there is
no configuration C ∈ (Lh−i , Rh+i ) which is supported by a configuration
C 0 ∈ (Lh−i−j , Rh+i+j ).

(ii) At the beginning of the iteration, for all 0 ≤ i < h, we have that
w(Lh−i , Rh+i ) = w(Lh−i , h, i) and for all 0 < i0 ≤ h − i,

w(Lh−i , h − i0 , i + i0 ) = w(Lh−i , h, i) + i0 · . (3.11)

Let us get some intuition behind this definition. The first condition im-
plies that during good iterations the work function values of configurations
(Lh−i , Rh+i ) are not affected by configurations (Lh−j , Rh+j ) for j 6= i. This
makes it easier to argue about w(Lh−i , Rh+i ). Moreover, by basic properties, it
implies that the WFA does not move servers from L to R (see Observation 3.25
below). Since the WFA has h servers in R when Step 2 starts, our goal is to
show that there are too many consecutive good iterations in the beginning
of Step 2. This implies that for the largest part of Step 2, the WFA has h
servers in R. Then, it suffices to get a lower bound on the cost of the WFA
during those iterations. The second condition implies that at the beginning
of a good phase, any optimal schedule for configurations (Lh−i , Rh+i ) is at a
configuration (Lh−i , h, i).
We now state some basic observations that follow from the definition of a
good iteration and will be useful in our analysis.

Observation 3.25. During a good iteration the WFA does not move any server
from L to R.

To see why this is true, consider any time during the iteration when the
WFA moves from a configuration C to C 0 , such that C ∈ (Lh−i , Rh+i ), for some
0 ≤ i < h. By basic properties of work functions, C is supported by C 0 . Since
the iteration is good, C is not supported by any configuration (Lh−i−j , Rh+i+j ),
i.e. C 0 ∈
/ (Lh−i−j , Rh+i+j ). Thus the WFA does not move a server from L to
R.
The following observation comes immediately from Corollary 3.23 and the
definition of a good iteration.

Observation 3.26. Consider a good iteration and let w, w0 be the work function
at the beginning and at the end of the iteration respectively. Then for all
0 ≤ i ≥ h we have that

w0 (Lh−i , Rh+i ) − w(Lh−i , Rh+i ) = 2(h − i).

52 3. The (h, k)-Server Problem on Bounded Depth Trees

Moreover, using Lemma 3.22 for c = 1, we get the following observation.

Observation 3.27. At the end of a good iteration, (3.11) holds.
The next lemma gives us a sufficient condition for an iteration to be good.
Lemma 3.28. Consider an iteration of Step 2 with initial work function w.
If w satisfies (3.11) and for all 0 ≤ i < h and 0 < j ≤ h − i,

w(Lh−i , Rh+i ) + 3 · h < w(Lh−i−j , Rh+i+j ) + j,

then the iteration is good.

Proof. Let t be any time during the iteration with work function w0 . For any
configuration C ∈ (Lh−i , Rh+i ), a possible schedule to that serves all requests
until time t and ends up in C is to simulate the optimal schedule ending up in
any configuration (Lh−i , Rh+i ), and then moving at most i ≤ h servers within
R. The cost of this schedule is at most

w0 (Lh−i , Rh+i ) + h ≤ w(Lh−i , Rh+i ) + 2(h − i) + h ≤ w(Lh−i , Rh+i ) + 3h,

(3.12)
where the first inequality holds due to Corollary 3.23. Since the right hand
side of (3.12) is smaller than w(Lh−i−j , Rh+i+j ) + j ≤ w0 (Lh−i−j , Rh+i+j ) + j,
we get that there is no configuration C ∈ (Lh−i , Rh+i ) which is supported by
a configuration (Lh−i−j , Rh+i+j ) and thus the iteration is good.

Counting good iterations We now count the number of consecutive good

iterations in the beginning of Step 2. For all 0 ≤ i < h and 0 < j ≤ h − i,
let Di,j = w(Lh−i , Rh+i ) − w(Lh−i−j , Rh+i+j ). The next lemma estimates the
change in Di,j after a good iteration.
Lemma 3.29. Consider a good iteration and let w, w0 be the work function
at the beginning and at the end of the iteration. Then, for all 0 ≤ i < h and
0 < j ≤ h − i, we have that
0
Di,j = w0 (Lh−i , Rh+i ) − w0 (Lh−i−j , Rh+i+j ) = Di,j + 2j.

Proof. By Observation 3.26 we have that

w0 (Lh−i , Rh+i ) − w0 (Lh−i−j , Rh+i+j ) =

= w(Lh−i , Rh+i ) + 2(h − i) − w(Lh−i−j , Rh+i+j ) − 2(h − i − j)
= w(Lh−i , Rh+i ) − w(Lh−i−j , Rh+i+j ) + 2j.

Now we are ready to estimate the number of consecutive good iterations

after Step 2 starts.
3.5. Lower Bounds 53

3h
Lemma 3.30. The first dN − 2 e iterations of Step 2 are good.

Proof. By Observation 3.27, we have that at the end of a good iteration, (3.11)
holds. Thus, by Lemma 3.28, if at the end of the current iteration Di,j < j−3h
for all 0 ≤ i < h, 0 < j ≤ h − i, then the next iteration is good.
At the beginning of Step 2, Di,j = −j, due to (3.10). From Lemma 3.29 we
have that after each good iteration, Di,j increases by 2j. Thus, all iterations
will be good, as long as Di,j < j − 3h. Since

3h 3h
(dN − e − 1) · 2j < (N − ) · 2j = 2j − 3jh ≤ 2j − 3h,
2 2

we get that at the beginning of the (dN − 3h

2 e)th iteration of Step 2, Di,j <
−j + 2j − 3h = j − 3h. Thus the first dN − 3h 2 e iterations of Step 2 are
good.

We get the following corollary.

Corollary 3.31. After dN − 3h

2 e iterations of Step 2, WFA still has h servers
in R.

This holds due to the fact that at the beginning of Step 2, the WFA has
h servers in R, and from Observation 3.25 we know that the WFA does not
move a server from L to R during good iterations.

Work function values for good iterations. Now we proceed to the cha-
racterization of the work function during good iterations. Since we want to
estimate the cost of the WFA during iterations when it has h servers at R,
we focus on configurations (Lh , Rh ). Specifically, we need the corresponding
versions of Lemmata 3.19, 3.20 and 3.21. Recall that, by definition of a good
iteration, the local changes in the values of w(Lh , Rh ), define the work function
values of all configurations (Lh , Rh ).
We begin with the corresponding versions of Lemmata 3.19 and 3.20 for
good iterations of Step 2.

Lemma 3.32. Consider a good iteration of Step 2. Let t1 be the time when
S(R2 , `, 2) ends, for 1 ≤ ` ≤ h and t2 the time when S(R2 , h, 2) ends. At
any time t ∈ [t1 , t2 ], we have that w(Lh , h − ` + 1, ` − 1) = w(Lh , h − `, `) + .

Proof. The proof is same as proof of Lemma 3.19 with replacing (Lk−i , Ri )
by (Lh , h − i, i), scaling distances by  and noting that by (3.11), any optimal
schedule for configurations (Lh , Rh ) starts the iteration from a configuration
(Lh , h, 0).
54 3. The (h, k)-Server Problem on Bounded Depth Trees

Lemma 3.33. Consider a good iteration of Step 2. Let t1 be the time when
S(R2 , `, 2) ends, for 1 ≤ ` ≤ h and t2 the time when S(R2 , h, 2) ends. At
any time t ∈ [t1 , t2 ], we have that, for any 1 ≤ i < `, w(Lh , h − i, i) =
w(Lh , h − `, `) + (` − i).

The proof of this lemma is same as the proof of Lemma 3.20, i.e. by
backwards induction on i. We just need to replace (Lk−i , Ri ) by (Lh , h − i, i)
and scale all distances by .
The next two lemmata are the analogues of Lemma 3.21 for good iterations
of Step 2, and characterize the structure of the work function at the end of
S(R2 , `, 2) and S(R1 , `, 2), for 1 ≤ ` ≤ h.

Lemma 3.34. Consider a good iteration during Step 2. At the moment when
the execution of S(R2 , `, 2) ends, for 1 ≤ ` ≤ h, the following two things hold:

1. For all 0 ≤ i < `, w(Lh , h − i, i) = w(Lh , h − `, `) + (` − i)

2. For all ` < i ≤ h, w(Lh , h − i, i) = w(Lh , h − `, `) + (i − `)

Proof. For 0 ≤ i < `, the lemma follows from Lemma 3.33. For i ≥ ` the proof
is same as proof of Lemma 3.21 by replacing w(Lk−i , Ri ) by w(Lh , h − i, i)
and using the fact that at the beginning of the iteration w(Lh , h − i, i) =
w(Lh , h, 0) +  · i.

Lemma 3.35. Consider a good iteration during Step 2. At the moment when
an execution of S(R1 , `, 2) ends, for 1 ≤ ` ≤ h, the following two things hold:

1. For all 0 ≤ i < `, w(Lh , i, h − i) = w(Lh , `, h − `) + (` − i)

2. For all ` ≤ i ≤ h, w(Lh , i, h − i) = w(Lh , `, h − `) + (i − `)

Proof. The proof is completely symmetric to the proof of Lemma 3.34. Note
that, due to Lemma 3.34, after S(R2 , h, 2) ends, i.e at the beginning of
S(R1 , 1, 2), we have that w(Lh , Rh ) = w(Lh , 0, h) and that w(Lh , h − i, i) =
w(Lh , 0, h) + (h − i), or equivalently

w(Lh , i, h − i) = w(Lh , 0, h) +  · i. (3.13)

Note that (3.13) is symmetric to w(Lh , h − i, i) = w(Lh , h, 0) +  · i, which we

used in proof of Lemma 3.34, so we can apply the symmetric proof.

End of the phase: We now show that at the end of the phase the work
function has the desired structure and that the WFA has all its 2h servers in
R, so a new right-to-left phase may start.
3.5. Lower Bounds 55

Lemma 3.36. After N iterations of Step 2, w(Lh−i , Rh+i ) = w(L0 , R2h ) +

(h − i) = 3h − i, for all 1 ≤ i ≤ h − 1.
Proof. By basic properties of work functions, w(Lh−i , Rh+i ) ≤ w(L0 , R2h ) +
(h − i). Assume for contradiction that there exists some i such that
w(Lh−i , Rh+i ) < w(L0 , R2h ) + (h − i). If there are many such i’s, we prove
the contradiction for the largest one and then we can repeat. This assumption
implies that for any j > i we have that
w(Lh−j , Rh+j ) + (j − i) = w(L0 , R2h ) + (h − j) + (j − i)
= w(L0 , R2h ) + (h − i) > w(Lh−i , Rh+i ).
Thus, the configuration C that defines the value of w(Lh−i , Rh+i ) is not sup-
ported by any configuration (Lh−j , Rh+j ) for j > i. Let S be the schedule that
defines the value of w(Lh−i , Rh+i ) = W (C). Since C is not supported by any
configuration (Lh−j , Rh+j ) for j > i, S uses exactly h + i servers in R. We now
evaluate the cost of S. Moving h + i servers from L to R costs h + i. Serving
Step 1 using h+i servers in R costs 0. By Lemma 3.22, the optimal way to serve
N iterations of Step 2 using h + i servers in R has cost 2N · (h − i) = 2(h − i).
Overall we get that w(Lh−i , Rh+i ) = h + i + 2(h − i) = 3h − i.
On the other hand, we have that w(L0 , R2h ) = 2h for the whole phase.
Thus
w(Lh−i , Rh+i ) = 3h − i = w(L0 , R2h ) + (h − i),
contradiction.
By setting i0 = h − i, Lemma 3.36 gives us that
0 0
w(Li , R2h−i ) = w(L0 , R2h ) + i0 , for 1 ≤ i0 ≤ h. (3.14)
Moreover, by setting i0 = 2h − i in (3.9), we get that for h < i0 ≤ 2h,
0 0
w(Li , R2h−i ) = w(Lh , Rh ) + i0 − h = w(L0 , R2h ) + h + i0 − h = w(L0 , R2h ) + i0 ,
(3.15)
where the first equality holds due to (3.14). From (3.14), (3.15), we get that
after N iterations of Step 2,
0 0
w(Li , R2h−i ) = w(L0 , R2h ) + i0 , for all 1 ≤ i0 ≤ 2h. (3.16)
Note that w(L0 , R2h ) does not change during the whole phase, since exactly
2h points of R are requested. Thus, (3.16) holds until the end of the phase
and then a new right-to-left phase may start, satisfying the assumption about
the initial work function. Last, to see that at the end of the phase the WFA
has all its 2h servers in R, assume that after N iterations of Step 2, it is in
0 0
some configuration (Li , R2h−i ) for some 0 ≤ i0 ≤ (h − 1). Since (3.16) holds
until the end of the phase, during the next iteration, the WFA moves to the
configuration (L0 , R2h ).
56 3. The (h, k)-Server Problem on Bounded Depth Trees

Bounding Costs
We now bound the online and offline costs. We begin with Step 1.
Lemma 3.37. During the time when the WFA uses ` < h servers in R, it
incurs a cost of at least (2 − 20 ) · `.
Proof. By construction of the phase, when the execution of S(R1 , ` + 1, 2)
starts, the WFA has ` servers in R. We evaluate the cost of the WFA during
the part of S(R1 , ` + 1, 2) when it has ` servers in R. Let t be the time when
the WFA moves its (` + 1)th server to R. Let w and w0 be the work functions
at the beginning of S(R1 , ` + 1, 2) and at time t respectively. We have that,

w0 (Lk−`−1 , R`+1 ) = w(Lk−`−1 , R`+1 ) = w(Lk−` , R` ) + 1, (3.17)

where the first equality comes from the fact that there are exactly ` + 1 points
of R requested since the beginning of the phase and the second by Lemma 3.21.
Let C be the configuration of the WFA at time t0 − 1. At time t, the WFA
moves a server by a distance of 1, thus by basic properties of work functions,
we have that w0 (C) = w0 (Lk−`−1 , R`+1 ) + 1. This combined with (3.17) gives
that
w0 (C) = w(Lk−` , R` ) + 2. (3.18)
Let X ∈ (Lk−` , R` ) be a configuration such that (i) w0 (X) = w0 (Lk−` , R` )
and (ii) X, C have their k − ` servers of L at the same points. Note that
X, C ∈ (Lk−` , `, 0), since R1 is the only subtree of R where requests have been
issued. Since both X and C have ` servers in R1 , and only ` + 1 leaves of R1
have been requested, we get that X and C can differ in at most one point. In
other words, d(X, C) ≤ 0 . By basic properties of work functions we get that

w0 (C) ≤ w0 (X) + d(X, C) ≤ w0 (Lk−` , R` ) + 0 . (3.19)

From (3.18), (3.19) we get that

w0 (Lk−` , R` ) − w(Lk−` , R` ) ≥ w0 (C) − 0 − (w0 (C) − 2) = 2 − 0 . (3.20)

Let S` be the optimal schedule to serve all requests from the beginning of
S(R2 , ` + 1, 2) until time t, using ` servers starting at t1 , . . . , t` . From (3.20)
we have that cost(S` ) ≥ 2 − 0 . All requests are located in ` + 1 leaves of an
elementary subtree (which is equivalent to the paging problem) in an adver-
sarial way. It is well known (see e.g. [19]) that the competitive ratio of any
online algorithm for the paging problem for such a sequence is at least `, i.e. it
has cost at least cost(S` ) − ` · 0 , where ` · 0 is the allowed additive term. This
implies that the cost incurred by the WFA is at least

` · cost(S` ) − ` · 0 ≥ `(2 − 0 ) − ` · 0 = (2 − 20 ) · `.

3.5. Lower Bounds 57

Lemma 3.17 (restated) During Step 1, ALG ≥ h2 −0 ·h(h−1) and ADV= h.

Proof. Clearly, ADV= h; the adversary moves h servers by distance 1 and then
serves all requests
Ph−1 at zero cost. By lemma 3.37 we get that WFA incurs a cost
0
of at least `=1 (2 − 2 ) · ` inside R. Moreover, it pays a movement cost of h
to move its h servers
Ph−1from L to R. Overall, we get
Ph−1 P that the 2online cost during
Step 1 is (2−20 ) `=1 `+h = 2 `=1 `+h−20 h−1 `=1 ` = h − 0 ·h(h−1).

We now focus on Step 2. We charge the WFA only for the first dN −
3h
2 e
iterations (when it uses h servers in R, due to Corollary 3.31), plus the
movement cost of the extra servers from L to R.

Lemma 3.38. Consider a good iteration of Step 2 such that the WFA uses
only h servers in R. During the time interval that WFA serves requests in
subtree R1 or R2 using ` servers, it incurs a cost of at least 2( − 0 )`.

Proof. The proof is similar to the proof of Lemma 3.37, with the following
modifications. We scale distances by , since now the servers move from R1 to
R2 (distance ) instead of moving from L to R1 (distance 1). We charge the
WFA for serving requests in R2 using ` servers during executions of S(R2 , ` +
1, 2), using Lemma 3.34 (instead of Lemma 3.21) and replacing (Lk−i , Ri ) by
(Lh , h − i, i). Similarly, we charge the WFA for serving requests in R1 using `
servers during executions of S(R1 , ` + 1, 2) using Lemma 3.35.

Lemma 3.39. Consider a good iteration of Step 2 such that the WFA uses
only h servers in R to serve the requests. The cost of the WFA in such an
iteration is at least 2 · h2 − 20 · (h − 1) · h.

Proof. From Lemma

Ph−1 3.38, we get that the cumulative cost for all executions
0
of S in R2 is `=1 2( −  )` +  · h, where the last  · h term counts the
cost of moving h servers from R1 to R2 . Similarly, the WFA incurs the same
cumulative cost during executions of S in R1 . We get that the total cost of the
WFA during the iteration is at least
h−1
X h−1
X h−1
X
0
0 · `


2· 2( −  )` +  · h = 2 · h + 4 ·`−4
`=1 `=1 `=1
2 h + (h − 1)h − 20 · (h − 1) · h = 2 · h2 − 20 · (h − 1) · h.

0
Lemma 3.18 (restated) During Step 2, ALG ≥ 2h2 + h − 3h3 − 2  · (h − 1) · h
and ADV = (2 + )h.

Proof. Second step consists of N + 1 = 1/ + 1 iterations, where in each one

of them the adversary incurs a cost of 2 · h. Thus the offline cost is (2 + 2)h.
58 3. The (h, k)-Server Problem on Bounded Depth Trees

Let us now count the online cost during Step 2. By Corollary 3.31, there
are at least dN − 3h 2 e iterations such that the WFA has h servers in R. By
lemma 3.39 we get that during each one of those iterations, the online cost is
at least 2 · h2 − 20 · (h − 1) · h. For the rest of Step 2, the WFA incurs a cost
of at least h, as it moves h servers from L to R. We get that overall, during
Step 2, the cost of WFA is at least
3h
(N − ) · (2 · h2 − 20 · (h − 1) · h) + h
2
=2N  · h2 − 2N 0 · (h − 1) · h − 3h3 + 30 h2 (h − 1) + h
0
≥2h2 + h − 3h3 − 2 · (h − 1) · h.


Remaining Proofs
We now prove Lemma 3.19, whose proof was omitted earlier. First, we state an
observation which follows directly from the definition of the left-to-right phase.
Observation 3.40. Let t be any time during a left-to-right phase with work
function w. If w(Lk−i , Ri ) = w(Lk−j , Rj ) + (j − i) for some 0 ≤ i < j ≤ k,
0 0
then for all j 0 such that i ≤ j 0 ≤ j we have that w(Lk−j , Rj ) = w(Lk−j , Rj ) +
(j − j 0 ).
0 0
To see why this is true, note that by basic properties w(Lk−j , Rj ) ≤
w(Lk−j , Rj ) + (j − j 0 ). Moreover, if strict inequality holds, we have that
0 0
w(Lk−j , Rj ) + (j 0 − i) < w(Lk−j , Rj ) + (j − j 0 ) + (j 0 − i) = w(Lk−i , Ri ).
0 0
We get that w(Lk−i , Ri ) − w(Lk−j , Rj ) > j 0 − i, a contradiction.
Lemma 3.19 (restated) Consider a left-to-right phase. At any time after the
end of strategy S(R1 , `, 2), for 1 ≤ ` ≤ h, we have that w(Lk−`+1 , R`−1 ) =
w(Lk−` , R` ) + 1.

Proof. We prove the lemma by induction. For the base case ` = 1, the lemma
is clearly true since any schedule serving requests uses at least one server at
R. We prove the lemma for 2 ≤ ` ≤ h, assuming that it is true for all values
1, . . . , ` − 1.
Let t be any time after the end of strategy S(R1 , `, 2), for 1 < ` ≤ h with
work function w. By basic properties of work functions, w(Lk−`+1 , R`−1 ) ≤
w(Lk−` , R` ) + 1. We will assume that w(Lk−`+1 , R`−1 ) < w(Lk−` , R` ) + 1 and
obtain a contradiction. The lemma then follows.
Assume that w(Lk−`+1 , R`−1 ) < w(Lk−` , R` ) + 1. Let S`−1 and S` be
the schedules that define the values of w(Lk−`+1 , R`−1 ) and w(Lk−` , R` )
respectively. Let C be a configuration (Lk−`+1 , R`−1 ) such that w(C) =
w(Lk−`+1 , R`−1 ). By Observation 3.40, C is not supported by any configura-
tion (Lk−i , Ri ), for i ≥ `. Also, by the inductive hypothesis, C is not supported
3.6. Tight Bounds for WFA on the Line 59

by configurations (Lk−i , Ri ) for i < ` − 1. We get that C is in the support of

w. Without loss of generality S`−1 is lazy, i.e. it moves a server only to serve
a request (this is a standard property, explained in the proof of Theorem 3.4).
Thus, from the beginning of the phase until time t, S`−1 never moves a server
from R to L. We get that S`−1 uses exactly ` − 1 servers in R. On the other
hand, by construction of the phase, S` has at least ` servers in R during the
execution of S(R1 , `, 2).
We now compare the costs of S`−1 and S` . Before S(R1 , `, 2) starts, the
schedules are the same, since there are exactly ` − 1 points of R requested.
During S(R1 , `, 2), S` incurs a cost of 1 to move a server from L to R and
then serves all requests at zero cost, while S`−1 incurs a cost of at least 2 (by
construction of the strategy). When S(R1 , `, 2) ends, the set of leaves of R1
occupied by servers of S`−1 is a subset of the leaves occupied by servers of
S` . Thus, the cost incurred by S` after the end of S(R1 , `, 2) is smaller or
equal to the cost incurred by S`−1 during the same time interval. Overall, we
get that cost(S`−1 ) ≥ cost(S` ) + 1, i.e., w(Lk−`+1 , R`−1 ) ≥ w(Lk−` , R` ) + 1, a
contradiction.

3.6 Tight Bounds for WFA on the Line

In this section we show that the lower bound of section 3.5.2 for the WFA can
also be applied on the line. Moreover we show that there exists a matching
upper bound.

Lower Bound. The lower bound strategy is the same as the one described
for depth-3 HSTs, we just need to replace subtrees by line segments. More
precisely, the lower bound strategy is applied in an interval I of length 1. Let
L and R be the leftmost and rightmost regions of I, of length /2, for   1.
Similarly, L1 , L2 and R1 , R2 are smaller regions inside L and R respectively.
Again, the distance between L1 and L2 (R1 and R2 resp.) is much larger
than their length. In each of those regions we focus on h points, where the
distance between 2 consecutive points is 0  . Whenever the adversary moves
to such a region, it places its servers those h equally spaced points inside it.
Similarly to the proof of Theorem 3.2, we can get a lower bound h + 1/3 on
the competitive ratio of the WFA on the line when k = 2h (the changes affect
only the dependence on terms involving  and 0 , which are negligible).

Upper Bound We now show an upper bound on the cost of WFA for the
(h, k)-server problem in the line, which is implied by combining results of [17,
51].
60 3. The (h, k)-Server Problem on Bounded Depth Trees

Most known upper bounds for the WFA do not bound the algorithm’s
actual cost directly. Instead, they bound its extended cost, defined as the
maximum increase of the work function value for any single configuration. To
define it formally, let w and w0 be the work functions before and after serving
the request at time t. Then, if M denotes the metric space, the extended cost
at time t is defined as follows:

ExtCost(t) = max {w0 (X) − w(X)} ,

X∈M k

and the total extended cost of a sequence of requests is

X
ExtCost = ExtCost(t) .
t

For a given sequence of requests, let WFAi and OPTi denote the overall cost
incurred by WFA and OPT using i servers respectively. Similarly, let ExtCosti
denote the total extended cost over configurations of i servers. Chrobak and
Larmore [31] showed that the extended cost satisfies the following inequality:

WFAi + OPTi ≤ ExtCosti . (3.21)

In [17] it was shown that WFA with h servers is h-competitive in the line
by proving the following inequality:

ExtCosth ≤ (h + 1) OPTh +O(1) (3.22)

Moreover, Koutsoupias [51] showed that the extended cost is a non-increasing

function of the number of servers, which implies

ExtCostk ≤ ExtCosth (3.23)

for all request sequences. Putting (3.21), (3.22) and (3.23) together, we get

WFAk + OPTk ≤ ExtCostk ≤ ExtCosth ≤ (h + 1) OPTh +O(1) ,

which implies that WFAk is (h + 1)-competitive. In fact, a slightly stronger

inequality holds:

WFAk ≤ (h + 1) OPTh − OPTk +O(1) .

Matching Bounds. We now show that the lower and upper bounds above
are matching for k = 2h. In particular, it suffices to show that for our lower
bound instance (h + 1/3)OPTh goes arbitrary close to (h + 1)OPTh − OPTk ,
or equivalently
3.7. Concluding Remarks 61

2OPTh
→ OPTk (3.24)
3
As we showed in the proof of theorem 3.2, for every phase of the lower
bound strategy, OPTh = (3 + 2) · h. Moreover it is clear that OPTk = 2h;
during a phase the minimum work function value using k = 2h servers increases
by exactly 2h. We get that

2OPTh 2 · (3 + 2) · h 3 + 2
= = 2h → 2h = OPTk .
3 3 3

3.7 Concluding Remarks

Several intriguing open questions remain, and we list some of them here.

Open Problem 3.1. Is the dependence on d in Theorem 3.3 necessary? In

other words, can we get a O(1)-competitive algorithm for depth-d trees for
k  h?

While Theorem 3.4 gives a separation between depth-1 and depth-2 trees,
it is unclear whether a lower bound which increases substantially with depth
is possible. Note that a lower bound of g(d) for depth d, where g(d) → ∞ as
d → ∞ (provided that h is large enough), would be very surprising. This would
imply that there is no O(1)-competitive algorithm for general metric spaces.

Open Problem 3.2. Can we get an o(h)-competitive algorithm for other me-
tric spaces?

An interesting metric is the line. Here, we showed that both DC and

the WFA have competitive ratio Ω(h), and we do not even know any good
candidate algorithm. Designing an algorithm with such a guarantee would be
very interesting. Very recently, Coester et. al. [34] showed a lower bound of
3.146 on the competitive ratio of deterministic algorithms for the (h, k)-server
problem in the line (for sufficiently large h), even if k/h → ∞. This improves
our lower bound of 2.4 for general metric spaces, and remains up to date the
best known lower bound for the (h, k)-server problem.
Chapter 4

Competitive Algorithms for

Generalized k-Server in
Uniform Metrics

4.1 Introduction
In the generalized k-server problem, we are given k-servers s1 , . . . , sk , where
server si lies in a metric space Mi with distance function di . At each time step
a request r = (r1 , r2 , . . . , rk ) ∈ M1 × . . . × Mk arrives and must be served by
moving some server si to the point ri ∈ Mi . The goal is to minimize the total
distance traveled by the servers.
The generalized k-server problem is a substantial generalization of the stan-
dard k-server problem. In particular, the k-server problem corresponds to the
to the special case when all the metrics are identical, M1 = . . . = Mk = M ,
and the requests are of the form (r, r, . . . , r), i.e., the k-tuple is identical in
each coordinate.
The generalized k-server problem can model a rich class of online problems,
for which the techniques developed for the standard k-server problem do not
apply, see e.g. [55]. For that reason, it is widely believed that a deeper under-
standing of this problem should lead to powerful new techniques for designing
online algorithms [55, 63]. According to Koutsoupias and Taylor [55], this pro-
blem “may act as a stepping stone towards building a robust (and less ad hoc)
theory of online computation”.

Previous Work
In their seminal paper, Koutsoupias and Taylor [55] studied the special case
where k = 2 and both the metrics M1 and M2 are lines. This is called the CNN

63
64 4. Competitive Algorithms for Generalized k-Server in Uniform Metrics

problem and it has attracted a lot of attention [4, 28, 48, 47]. They showed
that, even for this special case, the problem is qualitatively very different from
the standard k-server problem. In particular they showed that many successful
k-server algorithms or their natural generalizations are not competitive. They
also showed that no memoryless randomized algorithm is competitive, while it
is well-known that for the standard k-server problem in the line there exists
a k-competitive (against adaptive online adversaries) randomized memoryless
algorithm [35]. A similar result with a simpler analysis was discovered inde-
pendently by Chrobak and Sgall [33].

Lower Bounds: For the CNN problem, Koutsoupias and Taylor [55] showed
that the competitive ratio of any deterministic algorithm is at least 10.12. For
uniform metrics and arbitrary k, they showed that even when each Mi contains
n = 2 points, the competitive ratio is at least 2k − 1. For general metrics, the
Ω(k)
best known lower bound is 22 [12], and comes from the weighted k-server
problem (the weighted variant of the standard k-server problem). This problem
corresponds to generalized-k-server where the metric spaces are scaled copies
of each other, i.e. Mi = wi · M for some fixed M , and the requests have the
form (r, . . . , r).

Upper Bounds: Despite considerable efforts, competitive algorithms1 are

known only for the case of k = 2 servers [65, 63, 64]. In a breakthrough result,
Sitters and Stougie [65] obtained a O(1)-competitive algorithm for k = 2 in any
metric space. Recently, Sitters [63] showed that the generalized WFA is also
O(1)-competitive for k = 2 by a careful and subtle analysis of the structure
of work functions. Despite this progress, no f (k)-competitive algorithms are
known for k > 2, even for special cases such as uniform metrics and lines.

Our Results
We consider the generalized k-server problem on uniform metrics and obtain
the first f (k)-competitive algorithms for general k, whose competitive ratios
almost match the known lower bounds.
Perhaps surprisingly, there turn out to be two very different settings for
uniform metrics:

1. When all the metric spaces M1 , . . . , Mk are uniform (possibly with dif-
ferent number of points) with identical pairwise distance, say 1. We call
this the uniform metric case.
1
We focus on algorithms with competitive ratio f (k) that only depends on k. Note that
an nk − 1 competitive algorithm follows trivially, as the problem can be viewed as metrical
service system (MSS) on nk states, where n = maxki=1 |Mi |.
4.1. Introduction 65

2. When the metric spaces Mi are all uniform, but have different scales,
i.e. all pairwise distances in Mi are wi . We call this the weighted uniform
metric case.

Our first result is the following.

Theorem 4.1. There is a (k · 2k )-competitive deterministic algorithm for the

generalized k-server problem in the uniform metric case.

This almost matches the 2k − 1 lower bound due to [55] (we describe this
instructive and simple lower bound instance in Section 4.5 for completeness).
To prove Theorem 4.1, we divide the execution of the algorithm in phases,
and consider the beginning of a phase when all the MSS states are feasible
(e.g. the cost is 0 and not ∞). As requests arrive, the set of states that
remain feasible for all requests during this phase can only reduce. The proof is
based on a general combinatorial argument about how the set of feasible states
evolves as requests arrive. In particular, for this problem we show that any
sequence of requests that causes the set of feasible states to strictly reduce at
each step, can have length at most 2k until all states become infeasible.
Interestingly, this argument is based on a novel application of the poly-
nomial or the rank method from linear algebra [49, 58, 45]. While the rank
method has led to some spectacular recent successes in combinatorics and com-
puter science [36, 37], we are not aware of any previous applications to online
algorithms. We feel that our approach could be useful for other online problems
that can be modeled as metrical service systems by analyzing the combinatorial
structure in a similar way.
Next, we consider randomized algorithms against oblivious adversaries.

Theorem 4.2. There is a randomized algorithm for the generalized k-server

problem on uniform metrics with competitive ratio O(k 3 log k).

The rank method above does not seem to be useful in the randomized set-
ting as it only bounds the number of requests until the set of feasible states
becomes empty, and does not give any structural information about how the
set of states evolves over time. As we observe in Section 4.3, a o(2k ) gua-
rantee cannot be obtained without using such structural information. So we
explore the properties of this evolution more carefully and use it to design the
randomized algorithm in Theorem 4.2.
In Section 4.5, we also give a related lower bound. In particular, we note
that an Ω(k/ log2 k) lower bound on the competitive ratio of any randomized
algorithm follows directly by combining the lower bound instance of [55] with
the results of [16].
Finally, we consider the weighted uniform metric case.
66 4. Competitive Algorithms for Generalized k-Server in Uniform Metrics

k+3
Theorem 4.3. There is a 22 competitive algorithm for generalized k-server
on weighted uniform metrics.

Theorem 4.3 follows by observing that a natural modification of an algo-

rithm due to Fiat and Ricklin [43] for weighted k-server on uniform metrics also
works for the more general generalized k-server setting. Our proof is essentially
the same as that of [43], with some arguments streamlined and an improved
Ω(k)
competitive ratio2 . Finally, note that the 22 lower bound [12] for weighted
k-server on uniform metrics implies that the competitive ratio in Theorem 4.3
is essentially optimal.

4.2 Deterministic Algorithm for Uniform Metrics

In this section we prove Theorem 4.1. Recall that each Mi is the uniform metric
with unit distance. We assume that all metrics have n = maxki=1 |Mi | points
(if for some metric |Mi | < n, we can add some extra points that are never
requested). We use [n] to denote {1, . . . , n}. As the requests are arbitrary
k-tuples and each metric Mi is uniform, we can relabel the points arbitrarily
and hence assume that the set of points in each Mi is [n]. At any time t, the
state of an algorithm can be described by the k-tuple q t = (q1t , . . . , qkt ) where
for each i ∈ [k], qit ∈ [n] denotes the location of server i. Let rt = (r1t , . . . , rkt )
denote the request vector at time t. We need to find a state with the following
property:

Definition 4.4. A state q t satisfies (or is feasible for) the request rt if qit = rit
for some i ∈ [k].

Moreover, if the state changes from q t to q t+1 , the algorithm pays the
Hamming distance
d(q t+1 , q t ) = |{i : qit+1 6= qit }|,
between q t and q t+1 .
We describe a generic algorithm below that works in phases in Algorithm 2.
Each phase is independent of all other phases. For convenience we reset the
time at the beginning of each phase, i.e. we assume that the first request of
the phase is at time 1.
We will show that during each phase the offline optimum moves at least
once and hence pays at least 1, while the online algorithm changes its state at
most 2k times and hence pays at most k2k (as the Hamming distance between
any two states is at most k). It follows that for the whole request sequence,
4k
2
It was first pointed out to us by Chiplunkar [26] that the competitive ratio 22 claimed
k+O(1)
in [43] can be improved to 22 .
4.2. Deterministic Algorithm for Uniform Metrics 67

our algorithm pays at most c∗ · k2k + k2k , where c∗ denotes the optimal cost.
Here the additive term k2k accounts for the last (possibly unfinished) phase.

Algorithm 2: A deterministic k · 2k competitive algorithm.

If a phase begins, the algorithm starts in some arbitrary q 1 .
At each time t when a request rt arrives do the following.
if the current state q t does not satisfy the current request rt then
if there exists a state q that satisfies all requests r1 , . . . , rt then
Set q t+1 = q.
else
Set q t+1 to be an arbitrary location satisfying (only) rt .
End the current phase.
else
Set q t+1 = q t .

We call this algorithm generic as it can pick any arbitrary point q as long
as it is feasible for all requests of the current phase r1 , . . . , rt . Note that this
algorithm captures a wide variety of natural algorithms including (variants) of
the Work Function Algorithm.
Fix some phase that we wish to analyze, and let ` denote its length. Wit-
hout loss of generality, we can assume that any request rt causes the algorithm
to move, i.e. q t is not feasible for rt (removing requests where q t is feasible
does not affect the online cost, and can only help the offline adversary). So the
online algorithm moves exactly ` times. Moreover, the adversary must move at
least once during the phase as no location exists that satisfies all the requests
r1 , . . . , r` that arrive during the phase.
It suffices to show the following.
Theorem 4.5. For any phase as defined above, its length satisfies ` ≤ 2k .
Proof. We use the rank method. Let x = (x1 , . . . , xk ), y = (y1 , . . . , yk ) be
points in Rk , and consider the 2k-variate degree k polynomial p : R2k → R,
Y
p(x, y) := (xi − yi ).
i∈[k]

The key property of p is that a state q ∈ [n]k satisfies a request r ∈ [n]k iff
p(q, r) = 0.
We now construct a matrix M that captures the dynamics of the online
algorithm during a phase. Let M ∈ R`×` be an `×` matrix, where columns cor-
0
respond to the requests and rows to the states, with entries M [t, t0 ] = p(q t , rt ),
0
i.e., the [t, t0 ] entry of M corresponds to the evaluation of p on q t and rt
68 4. Competitive Algorithms for Generalized k-Server in Uniform Metrics

Claim 4.6. M is an upper triangular matrix with non-zero diagonal.

Proof. At any time t = 1, . . . , `, as the current state q t does not satisfy the
request rt , it must be that p(q t , rt ) 6= 0.
On the other hand, for t = 2, . . . , `, the state q t was chosen such that it
satisfied all the previous requests t0 for t0 < t. This gives that M [t, t0 ] = 0 for
t0 < t and hence all the entries below the diagonal are 0.
As the determinant of any upper-triangular matrix is the product of its
diagonal entries, this implies that M has non-zero determinant and has full
rank, rk(M ) = `.
However, we can use the structure of p to show that the rank of M is at most
2k in a fairly straight manner. In particular, we give an explicit factorization
of M as M = AB, where A is ` × 2k matrix and B is a 2k × ` matrix. Clearly,
as any m × n matrix has rank at most min(m, n), both A and B have rank at
most 2k . Moreover, as rk(AB) ≤ min(rk(A), rk(B)), this implies rk(M ) ≤ 2k .
It remains to show the factorization.
Indeed, if we express p(x, y) in terms of its 2k monomials, we can write
X
p(x, y) = (−1)k−|S| XS Y[k]\S ,
S⊆[k]
Q
where XS = i∈S xi with X∅ = 1, and YS is defined analogously.
Now, let A be the ` × 2k matrix with rows indexed by time t and columns
by subsets S ∈ 2[k] , with the entries
Y
A[t, S] = qSt := qit .
i∈S

Similarly, let B be the 2k × `

matrix with rows indexed by subsets S ∈ 2[k] and
columns indexed by time t0 . We define
t0 0
Y
B[S, t0 ] = (−1)k−|S| r[k]\S := (−1)k−|S| rit .
i∈[k]\S

Then, for any t, t0 ∈ [`],

0 0
X
M [t, t0 ] = p(q t , rt ) = (−1)k−|S| qSt r[k]\S
t
=
S⊆[k]
X
= A[t, S]B[S, t0 ] = (AB)[t, t0 ].
S⊆[k]

and hence M = AB as claimed.

We remark that an alternate way to view this result is that the length of
any request sequence that causes the set of feasible states to strictly decrease
at each step can be at most 2k .
4.3. Randomized Algorithm for Uniform Metrics 69

4.3 Randomized Algorithm for Uniform Metrics

In this section we give a randomized algorithm for uniform metrics with compe-
titive ratio O(k 3 log k). As in the previous section, we assume that all metrics
have the same number of points |Mi | = n. We also call a state feasible accor-
ding to Definition 4.4.
A natural way to randomize the algorithm from the previous section, would
be to pick a state uniformly at random among all the states that are feasible for
all the requests thus far in the current phase. The standard randomized uniform
MTS analysis [20] implies that this online algorithm would move O(log(nk )) =
O(k log n) times. However, this guarantee is not useful if n  exp(exp(k)).
Perhaps surprisingly, even if we use the fact from Section 4.2 that the
set of feasible states can shrink at most 2k times, this does not suffice to
give a randomized o(2k ) guarantee. Indeed, consider the algorithm that picks
a random state among the feasible ones in the current phase. If, at each
step t = 1, . . . , `, half of the feasible states become infeasible (expect the last
step when all states become infeasible), then the algorithm must move with
probability at least 1/2 at each step, and hence incur an expected Ω(`) = Ω(2k )
cost during the phase.
So proving a better guarantee would require showing that the scenario
above cannot happen. In particular, we need a more precise understanding of
how the set of feasible states evolves over time, rather than simply a bound on
the number of requests in a phase.
To this end, in Lemmata 4.7 and 4.9 below, we impose some stronger
subspace-like structure over the set of feasible states. Then, we use this struc-
ture to design a variant of the natural randomized algorithm above, that di-
rectly works with these subspaces.

Spaces of configurations. Let Ui denote the set of points in Mi . We

can
Qk think of U i = [n], but Ui makes the notation clear. We call a state Q in
k
i=1 Ui = [n] a configuration. Here we slightly abuse notation by letting
denote the generalized Cartesian product. It will be useful to consider sets of
configurations where some
Qk server locations are fixed at some particular loca-
tion. For a vector v ∈ i=1 (Ui ∪ {∗}), we define the space

k
( )
Y
S(v) := c∈ Ui ci = vi ∀i s.t. vi 6= ∗ .
i=1

A coordinate i with vi = ∗ is called free and the corresponding server can be

located at an arbitrary point of Ui . We call dimension the number of free
coordinates in the space S(v) and denote it with dim(S(v)).
70 4. Competitive Algorithms for Generalized k-Server in Uniform Metrics

Let us consider a d-dimensional space S and a request r such that some

configuration c ∈ S is not feasible for r. Then, we claim that a vast majority
of configurations from S are infeasible for r, as stated in the following lemma.
We denote F (r) the set of configurations satisfying r.

Lemma 4.7. Let S be a d-dimensional space and let r be a request which makes
some configuration c ∈ S infeasible. Then, there exist d subspaces S1 , . . . , Sd ,
each of dimension d − 1, such that we have S ∩ F (r) = S1 ∪ · · · ∪ Sd .

Note that |S| = nd and |Si | = nd−1 , i.e |Si | = n1 |S| for each i = 1, . . . , d.

Proof. By reordering the coordinates, we can assume that the first d coordi-
nates of S are free and S corresponds to the vector (∗, . . . , ∗, sd+1 , . . . , sk ), for
some sd+1 , . . . , sk . Let r = (r1 , . . . , rk ).
Consider the subspaces S(v1 ), . . . , S(vd ), where
v1 = (r1 , ∗, . . . , ∗, sd+1 , . . . , sk ),
..
.
vd = (∗, . . . , ∗, rd , sd+1 , . . . , sk ).
Clearly, any configuration contained in S(v1 ) ∪ . . . ∪ S(vd ), is feasible for r.
Conversely, as there exists c ∈ S infeasible for r, we have si = ci 6= ri for each
i = d + 1, . . . , k. This already implies that each configuration from S feasible
for r must belong to S(v1 ) ∪ . . . ∪ S(vd ): whenever c0 ∈ S is feasible for r, it
needs to have c0i = ri for some i ∈ {1, . . . , d} and therefore c0 ∈ S(vi ).

Spaces of feasible configurations. At each time t during a phase, we

maintain a set F t of spaces containing configurations which were feasible
with respect to the requests r1 , . . . , rt . In the beginning of the phase, we
set F 1 = {(r11 , ∗, . . . , ∗), . . . , (∗, . . . , ∗, rk1 )}, and, at time t, we update it in the
following way. We remove all spaces of dimension 0 whose single configuration
is infeasible w.r.t. rt . In addition, we replace each S ∈ F t−1 of dimension
d > 0 which contains some infeasible configuration by S1 , . . . , Sd according to
Lemma 4.7. The following observation follows easily from Lemma 4.7.

Observation 4.8. Let us consider a phase with requests r1 , . . . , r` . A configu-

ration c is feasible with respect to the requests r1 , . . . , rt if and only if c belongs
to some space in F t .

An alternative deterministic algorithm. Based on F t , we can design an

alternative deterministic algorithm that has a competitive ratio of 3(k + 1)!.
This is worse than the competitive ratio of Algorithm 2 but will be very useful
to obtain our randomized algorithm.
4.3. Randomized Algorithm for Uniform Metrics 71

We describe the alternative deterministic algorithm in Algorithm 3. In

contrast to the previous section, the algorithm is not defined in terms of phases,
and each time t corresponds to the tth request of the whole request sequence.
The partition of the request sequence into phases is made only for the analysis.
In particular, if a request rt causes F t to become empty, then we say that
the phase ends, we set F t = {(r1t , ∗, . . . , ∗), . . . , (∗, . . . , ∗, rkt )} and a new phase
starts. To serve a request at time t, the algorithm chooses some space Qt ∈ F t
and moves to an arbitrary state q t ∈ Qt . Whenever Qt−1 no more belongs to
F t , it moves to another space Qt regardless whether q t−1 stayed feasible or
not. While, this is not an optimal behavior, a primitive exploitation of the
structure of F t already gives a reasonably good algorithm.

Algorithm 3: Alternative deterministic algorithm.

at time t:
foreach S ∈ F t−1 containing some infeasible configuration do
// update F t for rt
replace S by S1 , . . . , Sd according to Lemma 4.7
if F t = ∅ then // start a new phase,
// if needed
F t := {S((r1t , ∗, . . . , ∗)), . . . , S((∗, . . . , ∗, rkt ))}
if Qt−1 ∈ F t then // serve the request
t
set Q := Q t−1 t
and q := q t−1

else
choose arbitrary Qt ∈ F t and move to an arbitrary q t ∈ Qt

The following lemma bounds the maximum number of distinct spaces which
can appear in F t during one phase.
Lemma 4.9. Let us consider a phase with requests rt1 , . . . , rt` . Then tt=t Ft
S`
1
contains at most k!/d! spaces of dimension d.
Note that this lemma implies that the competitive ratio of Algorithm 3 is
Pk−1 1
at most k · k! · d=0 d! ≤ 3kk! ≤ 3(k + 1)!, where the first factor k comes for
the fact that at each request the algorithm moves, it incurs a cost of at most
k.

Proof of Lemma 4.9. We proceed by induction on d. In the beginning, we have

k = k!/(k − 1)! spaces of dimension k − 1 in F 1 and, by Lemma 4.7, all spaces
added later have strictly lower dimension.
By the update rule on F t , each (d − 1)-dimensional
St` space is created from
t
some d-dimensional space already present in t=t1 F . By the inductive hypot-
hesis, there could be at most k!/d! distinct d-dimensional spaces and Lemma 4.7
72 4. Competitive Algorithms for Generalized k-Server in Uniform Metrics

implies that each of them creates at most d distinct (d − 1)-dimensional spa-

ces. Therefore, there can be at most k! k!
d! d = (d−1)! spaces of dimension d − 1 in
St` t
t=t1 F .

In fact, Algorithm 3 can be modified such that instead of choosing Qt and

qt arbitrarily, it chooses them in a way which ensures that it moves at most one
server in each request. This implies a slightly improved competitive ratio of 3k!.
We omit those details since we already know a deterministic algorithm with
competitive ratio k2k = o(k!) and our main focus here is to use the structure
of F t in order to get a randomized algorithm.

Randomized algorithm. Now we transform Algorithm 3 into a randomized

one. Let mt denote the largest dimension among all the spaces in F t and let
Mt denote the set of spaces of dimension mt in F t .
The algorithm works as follows: Whenever moving, it picks a space Qt from
Mt uniformly at random, and moves to some arbitrary q t ∈ Qt . As the choice
of q t is arbitrary, whenever some configuration from Qt becomes infeasible, the
algorithm assumes that q t is infeasible as well3 .

Algorithm 4: Randomized Algorithm for Uniform metrics.

at time t:
foreach S ∈ F t−1 containing some infeasible configuration do
// update F t for rt
replace S by S1 , . . . , Sd according to Lemma 4.7
if F t = ∅ then // start a new phase,
// if needed
F t := {S((r1t , ∗, . . . , ∗)), . . . , S((∗, . . . , ∗, rkt ))}
if Qt−1 ∈ Mt then // serve the request
set Qt := Qt−1 and q t := q t−1
else
Choose a space Qt from Mt uniformly at random
Move to an arbitrary q t ∈ Qt

At each time t, ALG is located at some configuration q t contained in some

space in F t which implies that its position is feasible with respect to the current
request rt , see Observation 4.8. Here is the key property about the state of
ALG.
3
This is done to keep the calculations simple, as the chance of Qt being removed from F
and q t staying feasible is negligible when k  n.
4.3. Randomized Algorithm for Uniform Metrics 73

Lemma 4.10. At each time t, the probability of Qt being equal to some fixed
S ∈ Mt is 1/|Mt |.
Proof. We prove the lemma by induction on t. For the base case t = 1, at the
first request the algorithm chooses a space Q1 from M1 uniformly at random
and the lemma follows.
Assume that the lemma is true for time t − 1. We will show that it holds
for time t. If ALG moved at time t, the statement follows trivially, since Qt
was chosen from Mt uniformly at random. It remains to consider the case that
Qt = Qt−1 .
Now, the algorithm does not change state if and only if Qt−1 ∈ Mt . More-
over, in this case mt does not change, and Mt ⊂ Mt−1 . By induction, Qt−1 is
distributed uniformly within Mt−1 , and hence conditioned on Qt−1 ∈ Mt , Qt
is uniformly distributed within Mt .

Proof of Theorem 4.2. Let cost(ALG) and cost(OPT) denote the cost of
the algorithm and the optimal solution respectively. At the end of each phase
(except possibly for the last unfinished phase), the set of feasible states F t = ∅,
and hence OPT must pay at least 1 during each of those phases. Denoting N
the number of phases needed to serve the entire request sequence, we have
cost(OPT) ≥ (N − 1). On the other hand, the expected online cost is at most,
E[cost(ALG)] ≤ c(N − 1) + c ≤ c cost(OPT) + c,
where c denotes the expected cost of ALG in one phase. This implies that
ALG is c-competitive.
Now we prove that c is at most O(k 3 log k). To show this, we use a potential
function
m
X t −1
t
Φ(t) = H(|M |) + H(k!/d!),
d=0
where H(n) denotes the nth harmonic number. At the beginning of the phase,
Φ(1) ≤ kH(k!) ≤ k(log k! + 1) = O(k 2 log k) as |M1 | ≤ k! and m1 ≤ k − 1.
Moreover the phase ends whenever Φ(t) decreases to 0. Therefore, it is enough
to show that, at each time t, the expected cost incurred by the algorithm is at
most k times the decrease of the potential. We distinguish two cases.
(i) If mt = mt−1 , let us denote b = |Mt−1 | − |Mt |. If b > 0, the potential
decreases, and its change can be bounded as
∆Φ ≤ H(|Mt |) − H(|Mt−1 |) =
1 1 1
=− t
− t
− ··· − t
|M | + 1 |M | + 2 |M | + b
1 1
≤ −b · = −b · .
|Mt | + b |Mt−1 |
74 4. Competitive Algorithms for Generalized k-Server in Uniform Metrics

On the other hand, the expected cost of ALG is at most k times the
probability that it has to move, which is exactly P [Qt−1 ∈ Mt−1 \ Mt ] =
b/|Mt−1 | using Lemma 4.10. Thus the expected cost of the algorithm is
at most k · b/|Mt−1 |, which is at most k · (−∆Φ).

(ii) In the second case, we have mt < mt−1 . By Lemma 4.9, we know that
|Mt | ≤ k!/mt ! and hence

∆Φ = H(|Mt |) − H(|Mt−1 |) − H(k!/mt !)

≤ −H(|Mt−1 |) ≤ −1,

since |Mt−1 | ≥ 1 and therefore H(|Mt−1 |) ≥ 1. As the expected cost

incurred by the algorithm is at most k, this is at most k · (−∆Φ).

4.4 Algorithm for Weighted Uniform Metrics

In this section we prove Theorem 4.3. Our algorithm is a natural extension
of the algorithm of Fiat and Ricklin [43] for the weighted k-server problem on
uniform metrics.

High-level idea. The algorithm is defined by a recursive construction based

on the following idea. First, we can assume that the weights of the metric
spaces are highly separated, i.e., w1  w2  . . .  wk (if they are not we
can make them separated while losing some additional factors). So in any
reasonable solution, the server sk lying in metric Mk should move much less
often than the other servers. For that reason, the algorithm moves sk only
when the accumulated cost of the other k − 1 servers reaches wk . Choosing
where to move sk turns out to be a crucial decision. For that reason, (in
each “level k-phase”) during the first part of the request sequence when the
algorithm only uses k − 1 servers, it counts how many times each point of
Mk is requested. We call this “learning subphase”. Intuitively, points of Mk
which are requested a lot are “good candidates” to place sk . Now, during the
next c(k) (to be defined later) subphases, sk visits the c(k) most requested
points. This way, it visits all “important locations” of Mk . A similar strategy
is repeated recursively using k − 1 servers within each subphase.

Notation and Preliminaries. We denote by sALG i and sADV

i the server
of the algorithm (resp. adversary) that lies in metric space Mi . Sometimes
we drop the superscript and simply use si when the context is clear. We set
k+2 k+1
Rk := 22 and c(k) := 22 −3 . Note that c(1) = 2 and that for all i,

4(c(i) + 1) · c(i) ≤ 8c(i)2 = c(i + 1). (4.1)

4.4. Algorithm for Weighted Uniform Metrics 75

Moreover, for all i ≥ 2, we have

Ri = 8 · c(i) · Ri−1 . (4.2)

We assume (by rounding the weights if necessary) that w1 = 1 and that for
2 ≤ i ≤ k, wi is an integral multiple of 2(1 + c(i − 1)) · wi−1 . Let mi denote
the ratio wi /(2(1 + c(i − 1)) · wi−1 ).
The rounding can increase the weight of each server at most by a factor of
4k−1 c(k−1)·. . .·c(1) ≤ Rk−1 . So, proving a competitive ratio Rk for an instance
k+3
with rounded weights will imply a competitive ratio Rk · Rk−1 < (Rk )2 = 22
for arbitrary weights.
Finally, we assume that in every request ALG needs to move a server. This
is without loss of generality: requests served by the algorithm without moving
a server do not affect its cost and can only increase the optimal cost. This
assumption will play an important role in the algorithm below.

4.4.1 Algorithm Description

The algorithm is defined recursively, where ALGi denotes the algorithm using
servers s1 , . . . , si . An execution of ALGi is divided into phases. The phases are
independent of each other and the overall algorithm is completely determined
by describing how each phase works. We now describe the phases.
ALG1 is very simple; given any request, ALG1 moves the server to the
requested point. For purposes of analysis, we divide the execution of ALG1
into phases, where each phase consists of 2(c(1) + 1) = 6 requests.

Phase of ALG1 :
for j = 1 to 2(c(1) + 1) do
Request arrives to point p: Move s1 to p.
Terminate Phase

We now define a phase of ALGi for i ≥ 2. Each phase of ALGi consists of

exactly c(i) + 1 subphases. The first subphase within a phase is special and we
call it the learning subphase. During each subphase we execute ALGi−1 until
the cost incurred is exactly wi .
During the learning subphase, for each point p ∈ Mi , ALGi maintains a
count m(p) of the number of requests r where p is requested in Mi , i.e. r(i) = p.
Let us order the points of Mi as p1 , . . . , pn such that m(p1 ) ≥ . . . ≥ m(pn ) (ties
are broken arbitrarily). We assume that |Mi | ≥ c(i) (if Mi has fewer points,
we add some dummy points that are never requested). Let P be the set of c(i)
most requested points during the learning subphase, i.e. P = {p1 , . . . , pc(i) }.
76 4. Competitive Algorithms for Generalized k-Server in Uniform Metrics

Phase of ALGi , i ≥ 2:
Move si to an arbitrary point of Mi ;
Run ALGi−1 until cost incurred equals wi ; // Learning subphase
For p ∈ Mi , m(p) ← # of requests such that r(i) = p; // Assume
m(p1 ) ≥ . . . ≥ m(pn )
P ← {p1 , . . . , pc(i) };
for j = 1 to c(i) do
Move si to an arbitrary point p ∈ P ;
P ← P − p;
Run ALGi−1 until cost incurred equals wi ; // (j + 1)th subphase
Terminate Phase

For the rest of the phase ALGi repeats the following c(i) times: it moves si
to a point p ∈ P that it has not visited during this phase, and starts the next
subphase (i.e. it calls ALGi−1 until its cost reaches wi ).

4.4.2 Analysis
We first note some basic properties that follow directly by the construction of
the algorithm. Call a phase of ALGi , i ≥ 2 complete, if all its subphases are
finished. Similarly, a phase of ALG1 is complete if it served exactly 6 requests.
Observation 4.11. For i ≥ 2, a complete phase of ALGi consists of (c(i) + 1)
subphases.
Observation 4.12. For i ≥ 2, the cost incurred to serve all the requests of a
subphase of ALGi is wi .
These observations give the following corollary.
Corollary 4.13. For i ≥ 1, the cost incurred by ALGi to serve requests of a
complete phase is 2(c(i) + 1)wi .
Proof. For i = 1 this holds by definition of the phase. For i ≥ 2, a phase
consists of (c(i) + 1) subphases. Before each subphase ALGi moves server si ,
which costs wi , and moreover ALGi−1 incurs a cost of wi .

Using this, we get the following two simple properties.

Lemma 4.14. By definition of ALG, the following properties hold:
1. A subphase of ALGi , i ≥ 2, consists of mi complete phases of ALGi−1 .

2. All complete phases of ALGi , i ≥ 1, consist of the same number of re-

quests.
4.4. Algorithm for Weighted Uniform Metrics 77

Proof. The first property uses the rounding of the weights. By Corollary 4.13,
each phase of ALGi−1 costs 2(c(i − 1) + 1)wi−1 and, in each subphase of ALGi ,
the cost incurred by ALGi−1 is wi . So there are exactly wi /(2(c(i − 1) +
1)wi−1 ) = mi phases of ALGi−1 .
The property above, combined with Observation 4.11 implies that a com-
plete phase of ALGi contains mi · (c(i) + 1) complete phases ALGi−1 . Now,
the second property follows directly by induction: each phase of ALG1 consists
of 2(c(1) + 1) = 6 requests, and each phase of ALGi consists of mi (c(i) + 1)
phases of ALGi−1 .

Consider a phase of ALGi . The next lemma shows that, for any point
p ∈ Mi , there exists a subphase where it is not requested too many times. This
crucially uses the assumption that ALGi has to move a server in every request.

Lemma 4.15. Consider a complete phase of ALGi , i ≥ 2. For any point

p ∈ Mi , there exists a subphase such that at most 1/c(i) fraction of the requests
have r(i) = p.

Proof. Let P be the set of c(i) most requested points of Mi during the learning
subphase. We consider two cases: if p ∈ P , there exists a subphase where
sALG
i is located at p. During this subphase there are no requests such that
r(i) = p, by our assumption that the algorithm moves some server at every
request. Otherwise, if p ∈/ P , then during the learning subphase, the fraction
of requests such that r(i) = p is no more than 1/c(i).

To show competitiveness of ALGk with respect to the optimal offline solu-

tion ADVk , the proof uses a subtle induction on k. Clearly, one cannot compare
ALGi , for i < k against ADVk , since the latter has more servers and its cost
could be arbitrarily lower. So the idea is to compare ALGi against ADVi ,
an adversary with servers s1 , . . . , si , while ensuring that, during time intervals
when ALGi is called by ALGk , ADVi is an accurate estimate of ADVk . To
achieve this, the inductive hypothesis is required to satisfy certain properties
described below. For a fixed phase, let cost(ALGi ) and cost(ADVi ) denote the
cost of ALGi and ADVi respectively.

(i) Initial Configuration of ADVi . Algorithm ALGi (for i < k), is called
several times during a phase of ALGk . As we don’t know the current con-
figuration of ADVk each time ALGi is called, we require that for every
complete phase, cost(ALGi ) ≤ Ri · cost(ADVi ), for any initial configura-
tion of ADVi .

(ii) The adversary can ignore a fraction of requests. During time

intervals when ALGi is called by ALGk , ADVk may serve requests with
servers si+1 , . . . , sk , and hence the competitive ratio of ALGi against
78 4. Competitive Algorithms for Generalized k-Server in Uniform Metrics

ADVi may not give any meaningful guarantee for ALGk . To get around
this, we will require that cost(ALGi ) ≤ Ri · cost(ADVi ), even if the ADVi
ignores an f (i) := 4/c(i + 1) fraction of requests. This will allow us to
use the inductive hypothesis for the phases of ALGi where ADVk uses
servers si+1 , . . . , sk to serve at most f (i) fraction of requests.

For a fixed phase, we say that ALGi is strictly Ri -competitive against

ADVi , if cost(ALGi ) ≤ Ri · cost(ADVi ). The key result is the following.

Theorem 4.16. Consider a complete phase of ALGi . Let ADVi be an adver-

sary with i servers that is allowed to choose any initial configuration and to
ignore any 4/c(i+1) fraction of requests. Then, ALGi is strictly Ri -competitive
against ADVi .

Before proving this, let us note that this directly implies Theorem 4.3.
Indeed, for any request sequence σ, all phases except possibly the last one, are
complete, so cost(ALGk ) ≤ Rk · cost(ADVk ). The cost of ALGk for the last
phase, is at most 2(c(k) + 1)wk , which is a fixed additive term independent of
the length of σ. So, ALGk (σ) ≤ Rk · ADVk (σ) + 2(c(k) + 1)wk , and ALGk
is Rk -competitive. Together with loss in rounding the weights, this gives a
k+3
competitive ratio of at mot (Rk )2 ≤ 22 for arbitrary weights.
We now prove Theorem 4.16.

Proof of Theorem 4.16. We prove the theorem by induction on k.

Base case (i = 1): As R1 > 6 and 4/c(2) = 1/8 ≤ 1/3, it suffices to show
here that ALG1 is strictly 6-competitive in a phase where ADV1 can ignore at
most 1/3 fraction of requests, for any starting point of sADV 1
1
.
By Corollary 4.13, we have cost(ALG1 ) = 2(c(1) + 1) = 6. We show
that cost(ADV1 ) ≥ 1. Consider two consecutive requests rt−1 , rt . By our
assumption that ALG1 has to move its server in every request, it must be that
rt−1 6= rt . So, for any t if ADV1 does not ignore both rt−1 and rt , then it
must pay 1 to serve rt . Moreover, as the adverary can chose the initial server
location, it may (only) serve the first request at zero cost. As a phase consists
of 6 requests, ADVi can ignore at most 6/3 = 2 of them, so there are at most 4
requests that are either ignored or appear immediately after an ignored request.
So among requests r2 , . . . , r6 , there is at least one request rt , such that both
rt−1 and rt are not ignored.
Inductive step: Assume inductively that ALGi−1 is strictly Ri−1 -competitive
against any adversary with i − 1 servers that can ignore up to 4/c(i) fraction
of requests.
Let us consider some phase at level i, and let I denote the set of requests
that ADVi chooses to ignore during the phase. We will show that cost(ADVi ) ≥
4.5. Lower Bounds 79

wi /(2Ri−1 ). This implies the theorem, as cost(ALGi ) = 2(c(i) +1)wi by Corol-

lary 4.13 and hence,
cost(ALGi ) 2(c(i) + 1)wi
≤ = 4(c(i) + 1)Ri−1
cost(ADVi ) wi /(2Ri−1 )
≤ 8 · c(i) · Ri−1 = Ri .

First, if ADVi moves server si during the phase, its cost is already at least wi
and hence more than wi /(2Ri−1 ). So we can assume that sADV i stays fixed at
some point p ∈ Mi during the entire phase. So, ADVi is an adversary that
uses i − 1 servers and can ignore all requests with r(i) = p and the requests of
I. We will show that there is a subphase where cost(ADVi ) ≥ wi /(2Ri−1 ).
By Lemma 4.15, there exists a subphase, call it j, such that at most 1/c(i)
fraction of the requests have r(i) = p. As all c(i) + 1 subphases have the same
number of requests (by Lemma 4.14), even if all the requests of I belong to
subphase j, they make up at most (4 · (c(i) + 1))/c(i + 1) ≤ 1/c(i) fraction of its
requests, where the inequality follows from equation (4.1). So overall during
subphase j, ADVi uses servers s1 , . . . , si−1 and ignores at most 2/c(i) fraction
of requests.
We now apply the inductive hypothesis together with an averaging argu-
ment. As subphase j consists of mi phases of ALGi−1 , all of equal length, and
ADVi ignores at most 2/c(i) fraction of requests of the subphase, there are at
most mi /2 phases of ALGi−1 where it can ignore more than 4/c(i) fraction of
requests. So, for at least mi /2 phases of ALGi−1 , ADVi uses i − 1 servers and
ignores no more than 4/c(i) fraction of requests. By the inductive hypothesis,
ALGi−1 is strictly Ri−1 -competitive against ADVi in these phases. As the
cost of ALGi−1 for each phase is the same (by Corollary 4.13), overall ALGi
is strictly 2Ri−1 competitive during subphase j. As the cost of ALGi during
subphase j is wi , we get that cost(ADVi ) ≥ wi /2Ri−1 , as claimed.

4.5 Lower Bounds

We present simple lower bounds on the competitive ratio of deterministic and
randomized algorithms for the generalized k-server problem in uniform metrics.

Deterministic Algorithms. We show a simple construction due to [55]

that directly implies a (2k − 1)/k lower bound on the competitive ratio of
deterministic algorithm. Using a more careful argument, [55] also improve this
to 2k − 1.
Assume that each metric space Mi has n = 2 points, labeled by 0,1. A
configuration of servers is a vector c ∈ {0, 1}k , so there are 2k possible con-
figurations. Now, a request r = (r1 , . . . , rk ) is unsatisfied if and only if the
80 4. Competitive Algorithms for Generalized k-Server in Uniform Metrics

algorithm is in the antipodal configuration r̄ = (1 − r1 , . . . , 1 − rk ). Let ALG

be any online algorithm and ADV be the adversary. Initially, ALG and ADV
are in the same configuration. At each time step, if the current configuration
of ALG is a = (a1 , . . . , ak ), the adversary requests ā until ALG visits every
configuration. If p is the configuration that ALG visits last, the adversary can
simply move to p at the beginning, paying at most k, and satisfy all requests
until ALG moves to p. On the other hand, ALG pays at least 2k − 1 until it
reaches p. Once ALG and ADV are in the same configuration, the strategy
repeats.

Randomized Algorithms. Viewing the generalized k-server problem as a

metrical service system (MSS), we can get a non-trivial lower bound for rand-
omized algorithms. In particular, we can apply the Ω( loglog 2
N
log N
) lower bound
due to Bartal et al. [16] on the competitive ratio of any randomized online
algorithm against oblivious adversaries, for any metrical task system on N
states. Of course, the MSS corresponding to a generalized k-server instance
is restricted as the cost vectors may not be completely arbitrary. However,
we consider the case where all metrics Mi have n = 2 points. Let s be an
arbitrary state among the N = 2k possible states. A request in the antipodal
point s only penalizes s and has cost 0 for every other state. So the space of
cost vectors here is rich enough to simulate any MSS on these N states (note
that if there is a general MSS request that has infinite cost on some subset S of
states, then decomposing this into |S| sequential requests where each of them
penalizes exactly one state of S, can only make the competitive ratio worse).
This implies an Ω( logk2 k ) lower bound for generalized k-server problem on
uniform metrics.

4.6 Conclusion and Open Problems

In this chapter we gave the first f (k)-competitive algorithms for uniform me-
trics, which attain (almost) optimal competitive ratios. The outstanding open
problem is the following:

Open Problem 4.1. Is there an f (k)-competitive algorithm for the generalized

k-server problem in general metric spaces?

This problem is interesting in the context of both deterministic and rando-

mized algorithms. In fact, answering this question requires the development of
powerful new techniques for online algorithms and could lead to a much deeper
theory of online computation.
Note that, even for the special case of the weighted k-server problem, no
competitive algorithms are known for k ≥ 3 beyond uniform metrics. Below,
4.6. Conclusion and Open Problems 81

we discuss some possible directions towards solving Open Problem 4.1.

Deterministic Algorithms. The only known candidate approach is to use

the work functions. Thus, showing competitiveness seems to require understan-
ding the structural and geometric properties of work functions. For example,
in [53] competitiveness of WFA for the k-server problem is shown using a so-
called quasi-convexity property. For more general problems similar properties
are not known (all known results are for k = 2 [33, 65, 63], where a careful case
analysis is applied). Such structural properties could be used either to show
that the generalized WFA is competitive, or to enable the design of a new al-
gorithm that uses the work functions. This could be for example a “dynamic”
WFA, which uses the (generalized) WFA by adjusting parameters online, or
any algorithm combined with WFA in an appropriate way (see e.g., [65, 24]).
As an intermediate step between uniform and arbitrary metric spaces, it
would be interesting to focus on some fixed metric which is more complex than
uniform metrics (e.g. weighted star, line). In fact, the line metric could be
an essential step towards generalizing to arbitrary metrics. It seems plausible
that understanding the weighted k-server case could enable the solution of the
generalized k-server problem. This was the case for k = 2 [63] and for weighted
uniform metrics, where in Section 4.4 we used a natural modification of the
weighted k-server algorithm to obtain a competitive algorithm.

Randomized Algorithms. The power of randomization in online algorithms

is much less understood, and there is not even of a candidate randomized al-
gorithm for the generalized k-server problem.
A natural first step is to understand the weighted uniform metric case.
It seems plausible that an exponential improvement compared to determi-
nistic algorithms is possible, i.e. it is natural to expect that there exists a
2poly(k) -competitive randomized algorithm against oblivious adversaries. Ho-
wever, even for the special case of the weighted k-server problem on uniform
k+O(1)
metrics, no better upper bound than 22 is known, and the best known
lower bound is only Ω(log k) and comes from the standard k-server in uniform
metrics! This motivates the following question.

Open Problem 4.2. What is the competitive ratio of randomized algorithms

for weighted uniform metrics?

Solving this problem seems to require non-trivial extensions of currently

known techniques for providing both upper and lower bounds on the competi-
tive ratio of randomized online algorithms.
Bibliography

[1] Dimitris Achlioptas, Marek Chrobak, and John Noga. Competitive analy-
sis of randomized paging algorithms. Theor. Comput. Sci., 234(1-2):203–
218, 2000.

[2] Susanne Albers. Improved randomized on-line algorithms for the list up-
date problem. SIAM J. Comput., 27(3):682–693, 1998.

[3] Susanne Albers and Jeffery Westbrook. Self-organizing data structures.

In Online Algorithms, The State of the Art, pages 13–51, 1996.

[4] John Augustine and Nick Gravin. On the continuous CNN problem. In
ISAAC, pages 254–265, 2010.

[5] Yossi Azar, Andrei Z. Broder, and Mark S. Manasse. On-line choice of
on-line algorithms. In Proceedings of the Fourth Annual ACM/SIGACT-
SIAM Symposium on Discrete Algorithms (SODA), pages 432–440, 1993.

[6] Nikhil Bansal, Niv Buchbinder, Aleksander Madry, and Joseph Naor. A
polylogarithmic-competitive algorithm for the k -server problem. J. ACM,
62(5):40, 2015.

[7] Nikhil Bansal, Niv Buchbinder, and Joseph Naor. Towards the rando-
mized k-server conjecture: A primal-dual approach. In Proceedings of
the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms,
SODA, pages 40–55, 2010.

[8] Nikhil Bansal, Niv Buchbinder, and Joseph Naor. A primal-dual rando-
mized algorithm for weighted paging. J. ACM, 59(4):19:1–19:24, 2012.

[9] Nikhil Bansal, Marek Eliáš, Lukasz Jeż, and Grigorios Koumoutsos. The
(h, k )-server problem on bounded depth trees. In Proceedings of the
Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
(SODA), pages 1022–1037, 2017.

83
84 Bibliography

[10] Nikhil Bansal, Marek Eliáš, Lukasz Jeż, Grigorios Koumoutsos, and Kirk
Pruhs. Tight bounds for double coverage against weak adversaries. In
Approximation and Online Algorithms - 13th International Workshop
(WAOA), pages 47–58, 2015.

[11] Nikhil Bansal, Marek Eliáš, Lukasz Jeż, Grigorios Koumoutsos, and Kirk
Pruhs. Tight bounds for double coverage against weak adversaries. Theory
Comput. Syst., 62(2):349–365, 2018.

[12] Nikhil Bansal, Marek Eliáš, and Grigorios Koumoutsos. Weighted k-server
bounds via combinatorial dichotomies. In 58th IEEE Annual Symposium
on Foundations of Computer Science (FOCS), pages 493–504, 2017.

[13] Nikhil Bansal, Marek Eliáš, Grigorios Koumoutsos, and Jesper Neder-
lof. Competitive algorithms for generalized k -server in uniform metrics.
In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA), pages 992–1001, 2018.

[14] Nikhil Bansal and Kirk Pruhs. Server scheduling to balance priorities,
fairness, and average quality of service. SIAM J. Comput., 39(7):3311–
3335, 2010.

[15] Yair Bartal. Probabilistic approximations of metric spaces and its al-
gorithmic applications. In 37th Annual Symposium on Foundations of
Computer Science (FOCS), pages 184–193, 1996.

[16] Yair Bartal, Béla Bollobás, and Manor Mendel. Ramsey-type theorems
for metric spaces with applications to online problems. J. Comput. Syst.
Sci., 72(5):890–921, 2006.

[17] Yair Bartal and Elias Koutsoupias. On the competitive ratio of the work
function algorithm for the k-server problem. Theor. Comput. Sci., 324(2–
3):337–345, 2004.

[18] Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, and
Avi Wigderson. On the power of randomization in on-line algorithms.
Algorithmica, 11(1):2–14, 1994.

[19] Allan Borodin and Ran El-Yaniv. Online computation and competitive
analysis. Cambridge University Press, 1998.

[20] Allan Borodin, Nathan Linial, and Michael E. Saks. An optimal on-line
algorithm for metrical task system. J. ACM, 39(4):745–763, 1992.

[21] Sébastien Bubeck, Michael B. Cohen, Yin Tat Lee, James R. Lee, and
Aleksander Madry. k-server via multiscale entropic regularization. In
Bibliography 85

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of

Computing (STOC), pages 3–16, 2018.

[22] Niv Buchbinder and Joseph Naor. The design of competitive online algo-
rithms via a primal-dual approach. Foundations and Trends in Theoretical
Computer Science, 3(2-3):93–263, 2009.

[23] Niv Buchbinder and Joseph Naor. Online primal-dual algorithms for co-
vering and packing. Math. Oper. Res., 34(2):270–286, 2009.

[24] William R. Burley. Traversing layered graphs using the work function
algorithm. J. Algorithms, 20(3):479–511, 1996.

[25] Jivitej S. Chadha, Naveen Garg, Amit Kumar, and V. N. Muralidhara. A

competitive algorithm for minimizing weighted flow time on unrelatedma-
chines with speed augmentation. In Proceedings of the Forty-first Annual
ACM Symposium on Theory of Computing (STOC), pages 679–684, 2009.

[26] Ashish Chiplunkar. Personal Communication. Oct 2016.

[27] Ashish Chiplunkar and Sundar Vishwanathan. On randomized memory-

less algorithms for the weighted k-server problem. In FOCS, pages 11–19,
2013.

[28] Marek Chrobak. SIGACT news online algorithms column 1. SIGACT

News, 34(4):68–77, 2003.

[29] Marek Chrobak, Howard J. Karloff, Thomas H. Payne, and Sundar

Vishwanathan. New results on server problems. SIAM J. Discrete Math.,
4(2):172–181, 1991.

[30] Marek Chrobak and Lawrence L. Larmore. An optimal on-line algorithm

for k-servers on trees. SIAM J. Comput., 20(1):144–148, 1991.

[31] Marek Chrobak and Lawrence L. Larmore. The server problem and on-line
games. In On-line Algorithms, volume 7 of DIMACS Series in Discrete
Mathematics and Theoretical Computer Science, pages 11–64. AMS/ACM,
1992.

[32] Marek Chrobak and Lawrence L Larmore. Metrical Service System: De-
terministic Strategies. Technical Report UCR-CS-93-1, Department of
Computer Science, College of Engineering, University of California, Ri-
verside, 1993.

[33] Marek Chrobak and Jiřı́ Sgall. The weighted 2-server problem. Theor.
Comput. Sci., 324(2-3):289–312, 2004.
86 Bibliography

[34] Christian Coester, Elias Koutsoupias, and Philip Lazos. The infinite server
problem. In 44th International Colloquium on Automata, Languages, and
Programming, ICALP, pages 14:1–14:14, 2017.

[35] Don Coppersmith, Peter Doyle, Prabhakar Raghavan, and Marc Snir.
Random walks on weighted graphs and applications to on-line algorithms.
J. ACM, 40(3):421–453, 1993.

[36] Z. Dvir. On the size of Kakeya sets in finite fields. J. Amer. Math. Soc.,
22:1093–1097, 2009.

[37] J. S. Ellenberg and D. Gijswijt. On large subsets of Fqn with no three-term

arithmetic progression. ArXiv e-prints, arXiv:1605.09223, 2016.

[38] Yuval Emek, Pierre Fraigniaud, Amos Korman, and Adi Rosén. On the
additive constant of the k -server work function algorithm. In Approxima-
tion and Online Algorithms, 7th International Workshop (WAOA), pages
128–134, 2009.

[39] Amos Fiat, Richard M. Karp, Michael Luby, Lyle A. McGeoch, Daniel Do-
minic Sleator, and Neal E. Young. Competitive paging algorithms. J.
Algorithms, 12(4):685–699, 1991.

[40] Amos Fiat and Manor Mendel. Better algorithms for unfair metrical task
systems and applications. SIAM J. Comput., 32(6):1403–1422, 2003.

[41] Amos Fiat, Yuval Rabani, and Yiftach Ravid. Competitive k-server algo-
rithms. J. Comput. Syst. Sci., 48(3):410–428, 1994.

[42] Amos Fiat, Yuval Rabani, Yiftach Ravid, and Baruch Schieber. A deter-
ministic o(k3 )-competitive k-server algorithm for the circle. Algorithmica,
11(6):572–578, 1994.

[43] Amos Fiat and Moty Ricklin. Competitive algorithms for the weighted
server problem. Theor. Comput. Sci., 130(1):85–99, 1994.

[44] Edward F. Grove. The harmonic online k-server algorithm is competi-

tive. In Proceedings of the 23rd Annual ACM Symposium on Theory of
Computing (STOC), pages 260–266, 1991.

[45] L. Guth. Polynomial Methods in Combinatorics. University Lecture Series.

American Mathematical Society, 2016.

[46] John Iacono. In pursuit of the dynamic optimality conjecture. In Space-

Efficient Data Structures, Streams, and Algorithms - Papers in Honor of
J. Ian Munro on the Occasion of His 66th Birthday, pages 236–250, 2013.
Bibliography 87

[47] Kazuo Iwama and Kouki Yonezawa. Axis-bound CNN problem. IEICE
TRANS, pages 1–8, 2001.

[48] Kazuo Iwama and Kouki Yonezawa. The orthogonal CNN problem. Inf.
Process. Lett., 90(3):115–120, 2004.

[49] Stasys Jukna. Extremal Combinatorics - With Applications in Compu-

ter Science. Texts in Theoretical Computer Science. An EATCS Series.
Springer, 2011.

[50] Bala Kalyanasundaram and Kirk Pruhs. Speed is as powerful as clairvoy-

ance. J. ACM, 47(4):617–643, July 2000.

[51] Elias Koutsoupias. Weak adversaries for the k-server problem. In Proc.
of the 40th Symp. on Foundations of Computer Science (FOCS), pages
444–449, 1999.

[52] Elias Koutsoupias. The k-server problem. Computer Science Review,

3(2):105–118, 2009.

[53] Elias Koutsoupias and Christos H. Papadimitriou. On the k-server con-

jecture. J. ACM, 42(5):971–983, 1995.

[54] Elias Koutsoupias and Christos H. Papadimitriou. The 2-evader problem.

Inf. Process. Lett., 57(5):249–252, 1996.

[55] Elias Koutsoupias and David Scot Taylor. The CNN problem and other
k-server variants. Theor. Comput. Sci., 324(2-3):347–359, 2004.

[56] James R. Lee. Fusible HSTs and the randomized k-server conjecture.
CoRR, abs/1711.01789, 2017.

[57] Mark S. Manasse, Lyle A. McGeoch, and Daniel D. Sleator. Competitive

algorithms for server problems. J. ACM, 11(2):208–230, 1990.

[58] Jiřı́ Matoušek. Thirty-three Miniatures: Mathematical and Algorithmic

Applications of Linear Algebra. American Mathematical Society, 2010.

[59] Lyle A. McGeoch and Daniel Dominic Sleator. A strongly competitive

randomized paging algorithm. Algorithmica, 6(6):816–825, 1991.

[60] Lee Newberg. The k-server problem with distinguishable servers. Master’s
Thesis, Univ. of California at Berkeley, 1991.

[61] Kirk Pruhs. Competitive online scheduling for server systems. SIGME-
TRICS Performance Evaluation Review, 34(4):52–58, 2007.
88 Bibliography

[62] Nick Reingold, Jeffery Westbrook, and Daniel Dominic Sleator. Rando-
mized competitive algorithms for the list update problem. Algorithmica,
11(1):15–32, 1994.

[63] René Sitters. The generalized work function algorithm is competitive for
the generalized 2-server problem. SIAM J. Comput., 43(1):96–125, 2014.

[64] René Sitters, Leen Stougie, and Willem de Paepe. A competitive algorithm
for the general 2-server problem. In ICALP, pages 624–636, 2003.

[65] René A. Sitters and Leen Stougie. The generalized two-server problem. J.
ACM, 53(3):437–458, 2006.

[66] Daniel Dominic Sleator and Robert Endre Tarjan. Amortized efficiency
of list update and paging rules. Commun. ACM, 28(2):202–208, 1985.

[67] Daniel Dominic Sleator and Robert Endre Tarjan. Self-adjusting binary
search trees. J. ACM, 32(3):652–686, 1985.

[68] Neal E. Young. The k-server dual and loose competitiveness for paging.
Algorithmica, 11(6):525–541, 1994.

[69] Neal E. Young. On-line file caching. Algorithmica, 33(3):371–383, 2002.

Summary

Algorithms for k-Server Problems

The topic of this thesis lies in the research area of optimization under un-
certainty. Uncertainty arises in many practical areas like resource allocation,
network design/maintenance and online advertising. In the presence of uncer-
tainty, we wish to take decisions whose outcome is as close as possible to the
optimal one we could achieve with full information. This is formalized in the
framework of competitive analysis of online algorithms.
An online algorithm receives the input over time and when an action is
needed, makes decisions without the knowledge of the future. The competitive
ratio of such an algorithm is the maximum ratio, over all input sequences, of
its cost to the optimal cost.
One of the most fundamental problems considered in competitive analysis
is the k-server problem. It is a generalization of various online problems and its
study has led to the development of generic techniques for online algorithms.
Here, there are k servers located at points of a given metric space. At each
time step, a request arrives at some point and must be served by moving a
server there. The goal is to minimize the total distance traveled by the servers.
This thesis contributes to the theory of online algorithms by obtaining
new results and designing new algorithms for several variants of the k-server
problem which were poorly understood, as discussed next.

The (h, k)-server problem. This is the resource augmentation version of

the k-server problem i.e., when the performance of the online algorithm with k
servers is compared to the offline optimal solution with h ≤ k servers. Classic
k-server results imply that for k = h the competitive ratio is Θ(h), and the
goal is to improve this guarantee as the ratio k/h increases. This was achieved
for trees of depth 1 (this special case corresponds to the weighted caching
problem), where many standard algorithms are roughly (1 + 1/)-competitive
when k = (1 + )h, for any  > 0. Surprisingly however, no o(h)-competitive
algorithm was known for any other metric space, even when (k/h) is arbitrarily
large. We obtain several new results for the problem.

89
90 Summary

In Chapter 2 we consider the Double Coverage (DC) algorithm, an elegant

algorithm for tree metrics, which is known to be h-competitive for k = h. We
show that, surprisingly, when k > h the competitive ratio of DC does not
improve; in particular, it is exactly k(h+1)
k+1 . Note that this ratio equals h for
k = h and increases up to h + 1 as k grows. In other words, the competitive
ratio of DC becomes strictly worse as the number of servers increases.
In Chapter 3 we focus on trees of bounded depth. Our motivation arises
from the fact that for trees of depth 1 we have a very good understanding
of the problem, but for arbitrary trees we don’t even know a good candidate
algorithm. Thus it is natural to study trees of small depth and try to get a
more systematic understanding of the problem. First, we consider the Double
Coverage (DC) algorithm and the Work Function Algorithm (WFA), which
are known to be O(h)-competitive for all trees for h = k. We show that
they both fail to improve their performance as k increases, and they have
competitive ratio Ω(h), even for trees of small depth. Then, by understanding
the drawbacks of those algorithms, we present a new algorithm that is O(1)-
competitive for constant depth trees, whenever k = (1+)h for any  > 0. This
is the first o(h)-competitive algorithm for any metric space other than trees of
depth 1. Finally, we show that the competitive ratio of any deterministic online
algorithm is at least 2.4 even for trees of depth 2 and when k/h is arbitrarily
large. This gives a surprising qualitative separation between trees of depth 1
and trees of depth 2 for the (h, k)-server problem.

The generalized k-server problem. This is a far-reaching extension of

the k-server problem, where each server si lies in its own metric space Mi .
A request is a k-tuple r = (r1 , r2 , . . . , rk ) and to serve it, we need to move
some server si to the point ri ∈ Mi . This problem can model a rich class of
online problems, for which the techniques developed for the standard k-server
problem do not apply, and it is widely believed that a deeper understanding of
this problem should lead to powerful techniques for designing online algorithms.
Despite much work, competitive algorithms were known only for k = 2.
In Chapter 4, we consider the problem on uniform metrics and present the
first f (k)-competitive algorithms for any value of k. In particular, we obtain a
deterministic algorithm for uniform metrics with competitive ratio k · 2k . This
ratio is almost optimal, since it is long-known that the competitive ratio of any
deterministic algorithm is at least 2k −1. Furthermore, we design a randomized
algorithm with competitive ratio O(k 3 · log k). Finally, we consider the case
where all metrics are uniform, but each one has different weight and we give a
k+3
deterministic algorithm with competitive ratio 22 , which essentially matches
k−4
the lower bound of 22 for this case.
Curriculum Vitae

Grigorios Koumoutsos was born on March 14, 1989 in Amarousion, Greece.

He studied Informatics and Telecommunications at the University of Athens,
where he graduated in July 2012. He continued his studies in Paris, France,
where he pursued the Parisian Master of Research in Computer Science (MPRI),
a master programme organized jointly by University Paris Diderot, École nor-
male supérieure (ENS) Paris, ENS Cachan, École Polytechnique and Telecom
Paris Tech. He obtained his Master’s degree in 2014 within the Algorithms
and Complexity group of University Paris Diderot under the supervision of
Adi Rosén.
Since September 2014 he has been a PhD student in the Combinatorial Op-
timization group of Eindhoven University of Technology under the supervision
of Nikhil Bansal.

91