On-Line Load Balancing in a Hierarchical Server Topology.
In a hierarchical server environment jobs are to be assigned in an on-line fashion to a collection of servers which form a hierarchy of capability: each job requests a specific server meeting its needs, but the system is free to assign it either to that server or to any other server higher in the hierarchy. Each job carries a certain load, which it imparts to the server it is assigned to. The goal is to find a competitive assignment in which the maximum total load on a server is minimized.We consider the linear hierarchy in which the servers are totally ordered in terms of their capabilities. We investigate several variants of the problem. In the unweighted (as opposed to weighted) problem all jobs have unit weight. In the fractional (as opposed to integral) model a job may be assigned to several servers, each receiving some fraction of its weight. Finally, temporary (as opposed to permanent) jobs may depart after being active for some finite duration of time. We show an optimal e-competitive algorithm for the unweighted integral permanent model. The same algorithm is (e+1)-competitive in the weighted case. Its fractional version is e-competitive even if temporary jobs are allowed. For the integral model with temporary jobs we show an algorithm which is  4-competitive in the unweighted case and 5-competitive in the weighted case. We show a lower bound of e for the unweighted case (both integral and fractional). This bound is valid even with respect to randomized algorithms. We also show a lower bound of 3 for the unweighted integral model when temporary jobs are allowed.We generalize the problem and consider hierarchies in which the servers form a tree. In the tree hierarchy, any job assignable to a node is also assignable to the node's ancestors. We show a deterministic algorithm which is 4-competitive in the unweighted case and 5-competitive in the weighted case, where only permanent jobs are allowed. Randomizing this algorithm improves its competitiveness to e and e+1, respectively. We also show an $\Omega(\sqrt{n})$ lower bound when temporary jobs are allowed.
Introduction
. One of the most basic on-line load-balancing problems is the
following. Jobs arrive one at a time and each must be scheduled on one of n servers.
Each job has a certain load associated with it and a subset of the servers on which it
may be scheduled. The goal is to assign jobs to servers so as to minimize the cost of
the assignment, defined as the maximum load on a server.
The nature of the load-balancing problem considered here is on-line: decisions
must be made without any knowledge of future jobs, and previous decisions may not
be revoked. We compare the performance of an on-line algorithm to the performance
of an optimal o#-line scheduler-one that knows the entire sequence of jobs in advance.
The e#cacy parameter of an on-line scheduler is its competitive ratio, roughly defined
# Received by the editors October 26, 1998; accepted for publication (in revised form) March 29,
2001; published electronically September 26, 2001. An extended abstract of this paper appeared in
Proceedings of the 7th European Symposium on Algorithms, Lecture Notes in Comput. Sci. 1643,
http://www.siam.org/journals/sicomp/31-2/34613.html
research.att.com). This author was on leave from the Electrical Engineering Department, Tel Aviv
University, Tel Aviv 69978, Israel.
# Computer Science Department, Technion, Haifa 32000, Israel (arief@cs.technion.ac.il, naor@cs.
technion.ac.il).
528 AMOTZ BAR-NOY, ARI FREUND, AND JOSEPH (SEFFI) NAOR
as the maximum ratio, taken over all possible sequences of jobs, between the cost
incurred by the algorithm and the cost of an optimal assignment.
1.1. The hierarchical servers problem. In the hierarchical servers problem
the servers form a hierarchy of capability; a job which may run on a given server may
also run on any server higher in the hierarchy. We consider the linear hierarchy in
which the servers are numbered 1 through n, and we imagine them to be physically
ordered along a straight line running from left to right, with server 1 leftmost and
server n rightmost. Leftward servers are more capable than rightward ones. We say
that servers 1, . , s are to the left of s, and that servers s are to the right
of s.
The input is a sequence of jobs, each carrying a positive weight and requesting
one of the servers. A job requesting server s can be assigned to any of the servers
to the left of s. These servers are the job's eligible servers. The assignment of a job
with weight w to server s increases the load on s by w (initially, all loads are 0). We
use the terms "job" and "request" interchangeably. The cost of a given assignment is
l s is the load on server s. We use OPT for the cost of an
optimal o#-line assignment. An algorithm is c-competitive if there exists some b > 0,
independent of the input, such that COST # c  OPT sequences. For
scalable problems (such as ours) the additive factor b may be ignored in lower bound
constructions.
We consider variants, or models, of the problem according to three orthogonal
dichotomies. In the integral model each job must be assigned in its entirety to a
single server; in the fractional model a job's weight may be split among several eligible
servers. In the weighted model jobs may have arbitrary positive weights; in the
unweighted model all jobs have unit weight. Our results for the fractional model hold
for both the unweighted and weighted cases, so we do not distinguish between the
unweighted fractional model and the weighted fractional model. Finally, permanent
jobs continue to load the servers to which they are assigned indefinitely; temporary
jobs are active for a finite duration of time, after which they depart. The duration
for which a temporary job is active is not known upon its arrival. We may allow
temporary jobs or we may restrict the input to permanent jobs only. When temporary
jobs are allowed, the cost of an assignment is defined as
where l s (t) is the load on server s at time t. The version of the problem which we
view as basic is the weighted integral model with permanent jobs only.
A natural generalization of the problem is for the servers to form a (rooted) tree
hierarchy ; a job requesting a certain server may be assigned to any of its ancestors in
the tree. The various models pertain to this problem as well.
The hierarchical servers problem is an important practical paradigm. It captures
many interesting applications from diverse areas such as assigning classes of service
to calls in communication networks, routing queries to hierarchical databases, signing
documents by ranking executives, and upgrading classes of cars by car rental
companies.
From a theoretical point of view, the hierarchical servers problem is also interesting
by virtue of its relation to the problem of related machines [3]. In this problem
all servers are eligible for every job, but they may have di#erent speeds; assigning a
job of weight w to a server with speed v increases its load by w/v. Without loss of
generality, assume is the speed of server i. Consider a
set of jobs to be assigned at a cost bounded by C, and let us focus on a particular
job whose weight is w. To achieve COST # C we must refrain from assigning this
LOAD BALANCING ON HIERARCHICAL SERVERS 529
job to any server i for which w/v i > C. In other words, there exists a rightmost
server to which we may assign the job. Thus, restricting the cost induces eligibility
constraints similar to those in the hierarchical servers problem. Some of the ideas
developed in the context of the hierarchical servers problems are applicable to the
problem of related machines, leading to better bounds for that problem [10].
1.2. Background. Graham [16] explored the assignment problem where each
job may be assigned to any of the servers. He showed that the greedy algorithm has
competitive ratio 2 - 1
. Later work [8, 9, 17, 2] investigated the exact competitive
ratio achievable for this problem for general n and for various special cases. The
best results to date for general n are a lower bound of 1.852 and an upper bound of
1.923 [2].
Over the years many other load-balancing problems were studied; see [4, 20]
for surveys. The assignment problem in which arbitrary sets of eligible servers are
allowed was considered by Azar, Naor, and Rom [7]. They showed upper and lower
bounds of #(log n) for several variants of this problem. Permanent jobs were assumed.
Subsequent papers generalized the problem to allow temporary jobs; in [5] a lower
bound of # n) and an upper bound of O(n 2/3 ) were shown. The upper bound was
later tightened to O( # n) [6].
The related machines problem was investigated by Aspnes et al. [3]. They showed
an 8-competitive algorithm based on the doubling technique. This result was improved
by Berman, Charikar, and Karpinski [12], who showed a more refined doubling algorithm
that is 3 5.828-competitive. By randomizing this algorithm, they were
able to improve the bound to 4.311. They also showed lower bounds of 2.438 (de-
terministic) and 1.837 (randomized). The randomized bound was recently improved
to 2 [14]. Azar et al. [6] generalized the problem to allow temporary jobs. They
showed a deterministic upper bound of 20 (which implies a randomized upper bound
of 5e # 13.59) and a lower bound of 3. The upper bounds were later improved to
The resource procurement problem was defined and studied by Kleywegt et al. [18]
independently of our work. In this problem jobs arrive over (discrete) time, each
specifying a deadline by which it must complete, and all jobs must be executed on a
single server. We can view this as a problem of assigning permanent jobs to parallel
servers if we think of the time slots as servers. In fact, the problem is equivalent
to the following variant of the hierarchical servers problem. The model considered
is the fractional model with permanent jobs only. The input consists of precisely n
jobs. The jth job to arrive specifies a server s servers eligible for
the job are s j , s In addition, the on-line nature of the problem
is less demanding. The scheduler need not commit to the full assignment of a job
immediately on its arrival. Rather, when the jth job arrives, it must decide what
fraction of each of the first j jobs to assign to server n 1. Kleywegt et al.
[18] developed a lower bound technique similar to ours and were able to establish a
lower bound of 2.51 by analytic and numerical means. They also described a 3.45-
competitive algorithm.
1.3. Our results. A significant portion of our work is devoted to developing a
continuous framework in which we recast the problem. The continuous framework
is not a mere relaxation of the problem's discrete features. Rather, it is a fully
fledged model in which a new variant of the problem is defined. The advantage of
the continuous model lies in the ability to employ the tools of infinitesimal calculus,
making analysis much easier.
In section 2 we use the continuous model to design an optimal e-competitive
algorithm. Surprisingly, this algorithm operates counterintuitively; the weight distribution
of an assigned job is biased to the left, i.e., more weight ends up on the
leftward servers. We show a general procedure for transforming an algorithm for the
continuous model into an algorithm for the fractional model. We also show a general
procedure for transforming an algorithm for the fractional model into an algorithm for
the integral model. Thus we get an e-competitive algorithm for the fractional model
and an algorithm which is, respectively, e and 1)-competitive for the unweighted
integral and weighted integral models. The former algorithm admits temporary jobs;
the latter does not. Our upper bound of e also applies to the resource procurement
problem of Kleywegt et al. [18] by virtue of Theorem 2 in their paper. Thus we
improve their best upper bound of 3.45.
In section 3 we develop a procedure for deriving lower bounds in the context of the
continuous model. The construction of the continuous model is rather unconventional
in its not being a generalization of the discrete model. In fact, on the surface of things,
the two models seem incomparable, albeit analogous. At a deeper level, though, it
turns out that the continuous model is actually a special case of the discrete model,
making lower bounds obtained in the continuous model valid in the discrete setting
as well. This makes the upper bound all the more intriguing, as it is developed in the
continuous framework and transported back to the discrete model. The lower bounds
obtained with our procedure are also valid in the discrete models (fractional as well
as integral), even in the unweighted case with permanent jobs only and even with
respect to randomized algorithms. Using our procedure we find that e is a tight lower
bound. Since our lower bound technique is the same as the one used (independently)
by Kleywegt et al. [18] in the context of the resource procurement problem, our lower
bound of e applies to that problem as well, and it improves their best lower bound of
2.51. Thus our work solves this problem completely by demonstrating a tight bound
of e.
In section 4 we consider temporary jobs in the integral model. We show a doubling
algorithm that is 4-competitive in the unweighted case and 5-competitive in the
weighted case. We also show a deterministic lower bound of 3.
Section 5 extends the problem to the tree hierarchy. We show an algorithm which
is, respectively, 4-, 4-, and 5-competitive for the fractional, unweighted integral, and
weighted integral models. Randomizing this algorithm improves its competitiveness
to e, e, and e + 1, respectively. We show lower bounds of # n) for all models, both
deterministic and randomized, when temporary jobs are allowed.
The e#ect of restricting the sets of eligible servers in several other ways is discussed
in section 6. In the three cases we consider, we show a lower bound of # log n). For
example, this lower bound holds in the case where the servers form a circuit (or a line)
and eligible servers must be contiguous. Note that since these problems are all special
cases of the problem considered in [7], an upper bound of O(log n) is immediate.
2. Upper bounds. In this section we show an algorithm whose respective versions
for the fractional, unweighted integral, and weighted integral models are e, e,
1)-competitive. The fractional version admits temporary jobs; the integral
versions do not. We build up to the algorithm by introducing and studying the
semicontinuous model and the class of memoryless algorithms. We begin with the
optimum lemma, which characterizes OPT in terms of the input sequence.
2.1. The optimum lemma. For the fractional and unweighted integral models
the lemma provides an exact formula for OPT . For the weighted integral case it gives
LOAD BALANCING ON HIERARCHICAL SERVERS 531
a 2-approximation. 1 The optimum lemma is a recurrent theme in our exposition.
For a given input sequence and a given server s, denote by W s the total weight
of jobs requesting servers to the left of s, and let  { s }.
Clearly, H is a lower bound on OPT , and in the unweighted integral model we can
tighten this to #H#. In addition, the maximum weight of a job in the input sequence,
denoted w max , is also a lower bound on OPT in the integral model.
Turning to upper bounds on OPT , let us say that a given server is saturated
at a given moment if its load is at least H. For the integral model, consider an
algorithm that assigns each job to its rightmost unsaturated eligible server. This
algorithm treats the jobs in an on-line fashion but requires advance knowledge of H
so it is o#-line. Clearly, if an unsaturated eligible server can always be found, then
COST < H +w max . We claim that this is indeed the case. To see this, suppose that
when some job of weight w arrives, all of its eligible servers are saturated. Let s be
maximal such that the servers to the left of s are all saturated. By the maximality
of s, the jobs assigned to the left of s must have all requested servers to the left of
s. Since their total weight is at least s  H, we have W s # s
contradiction.
For the fractional model we modify the above algorithm as follows. When a job
of weight w arrives, we assign it as follows: let s be the rightmost unsaturated eligible
server and let l s is the current load on s. If # w, we assign the
job in its entirety to s. Otherwise, we split the job and assign # units of weight to
s and treat the remainder recursively as a new job to be assigned. This algorithm
achieves COST # H.
The optimum lemma summarizes these results.
. In the fractional model,
. In the unweighted integral model,
. In the weighted integral model,
2.2. Memoryless algorithms. A memoryless algorithm is an algorithm that
assigns each job independently of previous jobs. Of course, memoryless algorithms
are only of interest in the fractional model, which is the model we are going to consider
here. We focus on a restricted type of memoryless algorithms, namely, uniform
algorithms. Uniform memoryless algorithms are instances of the generic algorithm
shown below; each instance is characterized by a function u
Algorithm GenericUniform
When a job of weight w requesting server s arrives, do:
1. r w; i s.
2. While r > 0:
3. Assign a = min {w  u(i), r} units of weight to server i.
4. r r - a.
5.
1 It is unreasonable to expect an easily computable formula for OPT in the weighted integral
model, for that would imply a polynomial-time solution for the NP-hard problem PARTITION
532 AMOTZ BAR-NOY, ARI FREUND, AND JOSEPH (SEFFI) NAOR
The algorithm starts with the server requested by the job and proceeds leftward
as long as the job is not fully assigned. The fraction of the job's weight assigned
to server i is u(i), unless w  u(i) is more than the remainder of the job when i is
reached. The condition ensures that the job will always be fully assigned by
the algorithm.
Note that the assignment generated by a uniform memoryless algorithm is independent
of both the number of servers and the order of jobs in the input. Moreover,
any collection of jobs with total weight w, requesting some server s, may be replaced
by a single request of weight w for s. We therefore assume that exactly one job requests
each server (we allow jobs of zero weight) and that the number of servers is
infinite. We denote the weight of the job requesting server s by w s .
Consider a job of weight w requesting a server to the right of a given server s. If
the requested server is close to s the job will leave wu(s) units of weight on s regardless
of the exact server requested. At some point, however, the job's contribution to the
load on s will begin to diminish as the distance of the request from s grows. Finally, if
the request is made far enough away, it will have no e#ect on s. We denote by p s the
point beyond which the e#ect on s begins to diminish and by p # s the point at which
it dies out completely:
Note that p s and p # s may be undefined, in which case we take them to be infinity. We
are interested only in functions u satisfying p s < # for all s.
The importance of p s lies in the fact that the load on s due to jobs requesting
servers in the range s, . , p s is simply u(s) times the total weight of these jobs. The
following lemma and corollary are not di#cult to prove.
(worst case lemma). Let A be a uniform memoryless algorithm. The
following problem,
Given K > 0 and some server s, find an input sequence I that maximizes
the load on s in A's assignment subject to
is solved by I
and l s -the resultant load on s-satisfies p s
Corollary 3. Let A be a uniform memoryless algorithm, and let CA be the
competitive ratio of A. Then sup
2.3. The semicontinuous model. In both the fractional and the integral versions
of the problem, the servers and the jobs are discrete objects. We therefore refer
to these models as the discrete models. In this section we introduce the semicontinuous
model, in which the servers are made continuous. In section 3 we define the
continuous model by making the jobs continuous as well.
The semicontinuous model is best understood through a physical metaphor. Consider
the bottom of a vessel filled with some nonuniform fluid applying varying degrees
of pressure at di#erent points. The force acting at any single point is zero, but any
LOAD BALANCING ON HIERARCHICAL SERVERS 533
region of nonzero area su#ers a net force equal to the integral of the pressure over
the region. Similarly, in the semicontinuous model we do not talk about individual
servers; rather, we have a continuum of servers, analogous to the bottom of the vessel.
An arriving job is analogous to a quantity of fluid which must be added to the vessel.
The notions of load and weight become divorced; load is analogous to pressure and
weight is analogous to force.
Formally, the server interval is [0, #), to which jobs must be assigned. Job j has
weight w j , and it requests the point s j > 0 in the server interval. The assignment of
job j is specified by an integrable function
2. x > s
3. g j is continuous from the right at every point.
The full assignment is . For a given full assignment g, the load l I on an
defined as l I
x
g(z) dz-the mean
weight density over I. The load at a point x is defined as l
g(x) . (We introduce the notation l x for consistency with previous notation.) The
cost of the assignment is
Lemma 4 (optimum lemma: semicontinuous model). Let W (x) be the total weight
of requests made to the left of x (including x itself ) and
Proof. The lower bound is trivial. For the upper bound, let x 1 # x 2 #    be the
points requested by the jobs and rearrange the jobs such that the jth job requests x j .
The idea is to pack the jobs (in order) in a rectangle extending from the left end of the
server interval. Let #
consider the following assignment:
This assignment clearly attains It follows from the definition of H that
all j, which is su#cient for the assignment's validity.
We adapt the definition of uniform memoryless algorithms to the semicontinuous
model. In this model a uniform algorithm is characterized by a function
(0, #) as follows. For a given point x > 0, let q(x) be the point satisfying the equation
1. Then the assignment of job j is
For q(x) and g j to be defined properly we must require that #
. (Otherwise, the algorithm may fail to fully assign jobs requesting points close
to 0.) Note that the load at 0 is always zero.
For a given point x > 0, we define p(x) as the point such that # p(x)
x
If p(x) does not exist, then the algorithm's competitive ratio is unbounded, as demonstrated
by the request sequence consisting of m # jobs, each of unit weight, where
the jth job requests the point s j. For this sequence, l
We shall therefore allow only algorithms satisfying #
all M # 0.
The semicontinuous model has the nice property that p s and p # s , which were
disparate in the discrete model, fuse into a single entity, p(s). The worst case lemma
and its corollary become the following lemma.
Lemma 5 (worst case lemma: semicontinuous model). Let A be a uniform memoryless
algorithm defined by u(x). The following problem,
Given K > 0 and some point s > 0 in the server interval, find an
input sequence that maximizes the load at s in A's assignment, subject
to
is solved by a single job of weight p(s)K requesting the point p(s), and the resultant
load at s is p(s)Ku(s).
Corollary 6. The competitive ratio of A is sup x {p(x)u(x)}.
2.4. An e-competitive algorithm for the semicontinuous model. Consider
Algorithm Harmonic, the uniform memoryless algorithm defined by
Let us calculate p(x):
x
dz
z
x
Thus, the competitive ratio of Algorithm Harmonic is sup x # ex 1
2.5. Application to the discrete models. Having devised a competitive algorithm
for the semicontinuous model, we wish to import it to the discrete model.
We start by showing how to transform any algorithm for the semicontinuous model
into an algorithm for the (discrete) fractional model. Following that, we show how
any algorithm for the fractional model may be transformed into an algorithm for the
integral models.
Semicontinuous to fractional. Let I be an input sequence for the fractional
model. If we treat each server as a point on (0, #), that is, we view a request for
server s as a request for the point s, then we can view I as a request sequence for the
semicontinuous model as well. By the respective optimum lemmas (Lemmas 1 and 4),
the value of OPT is the same for both models.
Let A be a c-competitive online algorithm for the semicontinuous model. Define
algorithm B for the fractional model as follows. When job j arrives, B assigns
units of weight to server i, for all i, where g j is the assignment function
generated by A for the job. Clearly, the cost incurred by B is bounded by the cost
incurred by A. Thus, B is c-competitive.
An important observation is that if A is memoryless, then so is B. Thus, even if
temporary jobs are allowed, the assignment generated by B will be c-competitive at
all times, compared to an optimal (o#-line) assignment of the active jobs.
We give the algorithm thus derived from Algorithm Harmonic the name Fraction-
alHarmonic.
Proposition 7. Algorithm FractionalHarmonic is e-competitive even when temporary
jobs are allowed.
Fractional to integral. Let A be an algorithm for the fractional model. Define
algorithm B for the integral model (both weighted and unweighted) as follows. As
jobs arrive, B keeps track of the assignments A would make. A server is said to be
overloaded if its load in B's assignment exceeds its load in A's assignment. When a
assigns it to the rightmost eligible server which is not overloaded (after
A is allowed to assign the job).
Proposition 8. Whenever a job arrives at least one of its eligible servers is not
overloaded.
LOAD BALANCING ON HIERARCHICAL SERVERS 535
Proof. Denote by l A
i (j) the load on server i after job j is assigned by
A and B, respectively. When job j is considered for assignment by B, server i is
overloaded
(j). Define A i
l A
(j).
We claim that for all j,
1. when job j arrives, server 1 (which is eligible) is not overloaded;
2. A i
The proof is by induction on j. The claim is clearly true for
some job j > 1 whose weight is w. We have l A
(j - 1), where the second inequality is justified by the induction hypothesis.
Thus, server 1 is not overloaded. It remains to show that for all i, A i
Let a be the rightmost server to which algorithm A assigns part of job j, i.e., a =
max{s | A s (j) > A s (j - 1)}. Let b be the server to which B assigns the job. By the
induction hypothesis, A i (j -
for all i, and B i
a and for i < b.
Assuming b < a, we still have to prove the claim for i # {b, . , a - 1}. Algorithm
assigns job j to server b and not to one of the servers b + 1, . , a, all of which are
eligible and to the right of b. It must therefore be the case that l A
(j - 1) for
a. Thus, for i # {b, . , a - 1},
a
l A
a
l A
> A a (j -
a
l B
a
l B
The second inequality is justified by the induction hypothesis.
Let w max (j) be the maximum weight of a job among the first j jobs. Algorithm
maintains l B
j. In the unweighted case we have
and in the weighted case w max # OPT . By the optimum lemma (Lemma 1)
the value of OPT in the integral model is at least as high as its value in the fractional
model. Thus if A is c-competitive, then B is c-competitive in the unweighted case
1)-competitive in the weighted case.
We give the algorithm thus derived from Algorithm FractionalHarmonic the name
IntegralHarmonic.
Proposition 9. Algorithm IntegralHarmonic is e-competitive in the unweighted
case and (e + 1)-competitive in the weighted case.
3. Lower bounds. In this section we devise a technique for proving lower
bounds in the limit n #. The bounds obtained are valid in both the fractional
and integral models, even in the unweighted case. In fact, they remain valid even
in the presence of randomization with respect to oblivious adversaries. Using this
technique, we obtain a tight constant lower bound of e. The success of our approach
is facilitated by transporting the problem from the discrete setting into a continuous
model, in which both jobs and servers are continuous.
3.1. A simple lower bound. We consider the fractional model, restricting our
attention to right-to-left input sequences, defined to be sequences in which for all
are made before any request for server i. We further
restrict our attention to sequences in which each server is requested exactly once. (We
allow jobs of zero weight.)
536 AMOTZ BAR-NOY, ARI FREUND, AND JOSEPH (SEFFI) NAOR
(b)
Fig. 1. (a) Histogram of job weights;
Let A be a k-competitive algorithm. For a given right-to-left input sequence,
denote by w s the weight of the job requesting server s and by l s the load on server s
at a given moment. Suppose the first n- (culminating with the request for
server i) have been assigned by A. Recall the definition of H in the optimum lemma
(Lemma 1); denote by h i the value of H with respect to these jobs. Since A is k-
competitive, the loads must obey l s # kh i for all s. For
Now consider the specific input sequence defined by w
w > 0. For this sequence, h Thus, after the first job is
assigned we have l n # kw/n. After the second job is handled we have l n-1 # 2kw/n,
but l n # kw/n still holds because the new job could not be assigned to server n. In
general, after the request for server s is processed, we have l i # (n
Noting that the total weight of the jobs in the input equals the total load
on the servers once the assignment is complete, we get
kw
kw
Hence, k # lim n# 2  n
2.
3.2. Discussion. Figure 1 depicts the request sequence and the resultant kh i 's
in histogram-like fashion with heights of bars indicating the respective values. The
bars are of equal width, so we can equivalently consider their area rather than height.
To be precise, let us redraw the histograms with bars of width 1 and height equal to
the numerical values they represent. Then, the total weight to be assigned is the total
area of the job bars, and the total weight actually assigned is bounded from above
by the total area of the kh i bars. Now, instead of drawing a histogram of kh i , let us
draw a histogram of h i . The lower bound is found by solving
total area of job bars # k  total area of h i bars,
total area of job bars
total area of h i bars
Note that if we multiply the weights of all jobs by some constant c > 0, the
heights of both the job bars and the h i bars will increase by a factor of c, leaving the
area ratio intact. Similarly, we can express the scaling of job weights by scaling the
width of the bars in both histograms. This, too, has no e#ect on the resultant ratio.
Thus we can express the entire procedure in geometric terms as follows. Select an
"input" histogram in which the width of each bar is 1
. Let h i,j be the area of bars
divided by j/n (the width of j bars), and let h
divide the area by j/n rather than j because h i is the height of the bar whose area
LOAD BALANCING ON HIERARCHICAL SERVERS 537
equals the value of OPT for the first n - Divide the area of the input
histogram by the area of the h i histogram (drawn to the same scale) to obtain a lower
bound. The scaling of the histograms allows us to keep considering finite areas as n
goes to infinity. This forms the link between the discrete model and the continuous
model, which we introduce next.
3.3. The continuous model. The continuous model is motivated by the observation
that the analysis suggested in the previous section tends to be exceedingly
di#cult for all but the simplest of input histograms. We turn to the continuous model
in order to avail ourselves of the machinery of infinitesimal calculus. The continuous
model di#ers from the semicontinuous model introduced in section 2 in two ways.
Instead of the infinite server interval, we use a finite interval [0, S], and, more impor-
tantly, jobs in the continuous model are not discrete; rather, we have a continuous
job flow arriving over time.
It is possible to define a general continuous model in which the arrival of jobs over
time is described by a function of place (in the server interval) and time. Although this
model is an interesting mathematical construction in its own right, we focus here on a
more restricted model-one that allows only the equivalent of right-to-left sequences.
Formally, the input is a request function, which is an integrable nonnegative real
function f(x) defined on the server interval [0, S]. The interpretation of f is by means
of integration, i.e., # x1
x0 f(x) dx is the total amount of weight requesting points in the
interval [x 0 , x 1 ]. The underlying intuition is that the request flow is right-to-left in
the sense that the infinitesimal request for point x is assumed to occur at "time"
Assignment are continuous too; an assignment is described by an assignment
function, which is an integrable nonnegative real function g(x) on [0, S) that (1) is
continuous from the right at every point and (2) satisfies # S
for all x 0 # [0, S) with equality for x algorithm in this model is an
algorithm which, given f(x), outputs g(x) such that for all x # [0, S), g(x) on the
interval [x, S) is independent of f(x) outside that interval. The definition of load and
cost are the same as in the semicontinuous model.
continuous model).
z
Proof. Let
z # zf(x) dx # and
H. In addition, the assignment function
achieves cost H.
Let us adapt the lower bound procedure from section 3.2 to the continuous model.
Consider a request function f(x) and the corresponding assignment g(x) generated
by some k-competitive on-line algorithm. We wish to bound the value of g(x) at some
fixed point a. Define a new request function
f a
a
with respect to f a equals h(a). (Note the analogy with h i,j and h i in the discrete
538 AMOTZ BAR-NOY, ARI FREUND, AND JOSEPH (SEFFI) NAOR
model.) da. The value of g in [a, S) must
be the same for f and f a , as g is produced by an on-line algorithm; thus g(a) # kh(a).
This is true for all a, hence,
from which the lower bound W/W # is readily obtained.
For certain request functions we can simplify the procedure. If f(x) is a continuous
monotonically decreasing function tending to 0 at some point x 0 # S (where x
is allowed), and we use f 's restriction to [0, S] as a request function, then we have the
following shortcut to h(a). Solve
d
db
h a
a f(x) dx
a
for b, and let b(a) be the solution. The following is easy to justify:
h(a) =b(a)
a
Note that if x 0 > S, this simplified procedure may return values for b(a) outside
the server interval [0, S]. In this case the true value of h(a) is less than the value
computed, leading to a less tight, but still valid, lower bound. We can therefore use
the simplified method without being concerned by this issue. Also, it is sometimes
more convenient to assume that the server interval, rather than being finite, is [0, #).
This too can be easily seen to make no di#erence, at least as far as using the simplified
procedure is concerned.
Example. Let
k . We find it easier to solve e
a
e -kx dx for a rather
than b:
# db.
Thus, setting z
z
is the familiar exponential integral function [1]. The
lower bound obtained is therefore
LOAD BALANCING ON HIERARCHICAL SERVERS 539
11. A lower bound of e can be obtained with our method by considering
the request function e -kx 1/k
in the limit k # with server interval [0, #).
Proof. For convenience we consider only integral values of k. We start by reviewing
some elementary facts concerning gamma functions [1]. The gamma function
is defined by
and it can be shown that for positive integer
1)!. The incomplete gamma function is defined by #(a,
z
dt. Integrating by parts we obtain the recurrence #(a
z a e -z . We also need Stirling's approximation:
Finally, consider the integral #
dx. Substituting
k# 1/k z k-1 e -z dz. Thus, for finite # and #,
Returning to our problem,
dx =k k-1
The relation between a and b is given by
be -kb 1/k
a
e -kx 1/k
Substituting r and t in the previous
equation and simplifying gives
Applying the recurrence to both sides of this equation and rearranging terms yields
We also get (directly)
Let us explore the relationship between r and t. Clearly, r # t. It is easy to see
that the function x k e -x increases in [0, k) and decreases in (k, #). Thus, referring to

Figure

2(a), we see that for r # k, #(k +1, r)-#(k+1,
r
is the area of
the region marked "X" between r and t, and r k e -r is the area of the dotted rectangle
between r and r + 1. Since both areas are equal and x k e -x decreases in this region,
Next consider r # k-2. Referring to Figure 2(b) and applying the same reasoning
we see that t # r+1 # k-1. Let us now consider the function x k-1 e -x . Its maximum
occurs at 1. Thus, since t # k - 1, the function increases in the interval [r, t].
Referring to Figure 2(c) and appealing to #(k, r) - #(k,
we see that
To summarize,
e -r ,
r
1-1/k .
(a)
(b)
(c)
Fig. 2. The relationship between r and t. The graphs are not drawn to the same scale. (a) Using
x k e -x to show r # k # t # r + 1. (b) Using x k e -x to show r # k - 2 # t # k - 1. (c) Using
x k-1 e -x to show
By di#erentiating we get
, which implies
r k-1 e -t dr # k
e
Putting all the pieces together,
#e -kb 1/k
da =W
dr
r k-1 e -t dr
r k-1 e -t dr #
e
+e
r k-1 e -r dr # .
Substituting
1-(1/k) in the first integral gives
1-(1/k)z k-1 e -z dz #e
Thus,
e
e
Hence, lim k#
e , and we obtain the lower bound lim k#
3.4. Application to the discrete models. Returning to the discrete setting,
we claim that lower bounds obtained using our method in the continuous model apply
in the discrete models as well. This is intuitively correct, since the continuous model
may be viewed as the limiting case of the integral models with n # and arbitrarily
long input sequences. We omit the proofs for lack of space.
We also claim that these lower bounds are valid even against randomized algo-
rithms. Whereas typical deterministic lower bound constructions are adversarial, that
is, a di#erent input sequence is tailored for each algorithm, our lower bound technique
provides a single sequence fit for all algorithms. Consequently, the bounds we derive
are also valid for randomized algorithms. This can be seen easily, either directly or
via Yao's principle (see, e.g., [13]).
LOAD BALANCING ON HIERARCHICAL SERVERS 541
4. Temporary jobs. In this section we allow temporary jobs in the input. We
restrict our attention to the integral model, as we have already seen (in section 2.5)
an optimal e-competitive algorithm for the fractional model that admits temporary
jobs. We present an algorithm that is 4-competitive in the unweighted case and 5-
competitive in the weighted case. We also show a lower bound of 3 for the unweighted
integral model.
Recall the definition of H in the optimum lemma (Lemma 1). Consider the jobs
which are active upon job j's arrival (including job j) and denote by H(j) the value
of H defined with respect to these jobs. A server is saturated on the arrival of job j
if its load is at least kH(j), where k is a constant to be determined later.
Algorithm PushRight
Assign each job it to its rightmost unsaturated eligible server.
Proposition 12. If k # 4, then whenever a job arrives, at least one of its eligible
servers is unsaturated. Thus, by taking
5)-competitive in the unweighted (resp. weighted) models.
Proof. We begin by considering the properties of certain sequences of numbers
whose role will become evident later. Consider the infinite sequence defined by the
recurrence a conditions a 1. We are
interested in the values of k for which this sequence increases monotonically. Solving
the recurrence reveals the following.
. If 4, then a
. If k > 4, then a
are the two roots of the quadratic
polynomial
. If k < 4, then a
It is easy to see that the sequence increases monotonically in the first two cases but
not in the third.
Now consider some infinite sequence {s i } obeying s
It is not di#cult to show that if k is chosen such that {a i }
increases monotonically, i.e., k # 4, then s i+2 # k(s
Returning to our proposition, let k # 4 and suppose that some job arrives, only
to find all of its eligible servers saturated. Let j 0 , be the first such job, and let s 1
be the server requested by it. We show how to construct two sequences, {s i } # i=0 and
with the following properties.
1.
2. For all i, although the servers s are all eligible for job j i , the
algorithm does not assign this job to the right of s i .
3. The jobs {j i } # i=1 are all distinct and they arrive before j 0 .
Property 3 states that job j 0 is preceded by an infinite number of jobs, yielding
a contradiction.
We have already defined Having defined
we define s i+2 and j i+1 as follows. Property 1 implies that s i < s
property 2 we know that when job arrives, the total weight of active jobs assigned
to servers s is at least k(s By the optimum lemma
(Lemma 1), at least one of these jobs must have requested a server whose number
is at least k(s any one such job and s i+2 as the server it
requests.
542 AMOTZ BAR-NOY, ARI FREUND, AND JOSEPH (SEFFI) NAOR
4.1. A lower bound. We show a lower bound of 3 on the competitive ratio
of deterministic algorithms. We use essentially the same construction as was used
in [6] in the context of related machines. Some of the details are di#erent, though,
owing to the di#erent nature of the two problems. For completeness, we present the
construction in full detail.
We consider the unweighted model. To motivate the construction, suppose the
value of OPT is known in advance and consider the algorithm that assigns each job
to its rightmost eligible server whose current load is less than k  OPT , where k # 1 is
an appropriately chosen constant. We design an input sequence targeted specifically
at this algorithm. As we shall see, the lower bound of 3 obtained using this input
sequence is valid for any on-line algorithm; we use only this algorithm to motivate
our construction.
Recall that a right-to-left input sequence is a sequence such that for all i < j,
all requests for server j are made before any of the requests for server i. Our input
sequence will be right-to-left. For now, we focus on the principles at the cost of rigor.
We shall refer to either of the servers s, s simply as server s. We will
also refer to server "x" without worrying about the fact that x may be noninteger.
To simplify matters, we design the sequence with OPT = 1. (This will be changed
later.)

Figure

3 depicts the first few steps in the ensuing construction.
(1)
kn
(2)
kn
kn
Fig. 3. The first two rounds in the input sequence.
We start by making requests to server n. Since OPT is already known to the
algorithm, we lose nothing by making n requests, which is the maximum permitted
by 1. The algorithm assigns these jobs to servers n(1 - 1
We now
remove #n jobs. (# will be determined shortly.) Naturally, the jobs we remove
will be the ones assigned rightmost by the algorithm. The remaining n(1 - #) jobs
will be the ones assigned to servers n(1 - 1
k . The adversary
assigns these jobs to servers #n, . , n. The value of # is determined by our desire
that the remaining jobs be assigned by the algorithm strictly to the left of their
assignment by the adversary. To that end, we select
k+1 , which solves the
equation
#n.
We proceed with a second round of jobs. The logical choice is to request server
n. We make #n requests, again, the maximum permitted by OPT = 1. The
algorithm assigns these jobs in the range n(1 - 1
#n of these jobs, the ones assigned rightmost by the algorithm. The remaining n(#)
jobs are assigned by the adversary in the range #n, . , #n and by the algorithm in the
range
. To determine # we solve n(1 - 1
LOAD BALANCING ON HIERARCHICAL SERVERS 543
(a)
(b)
Fig. 4. The ith round. Solid rectangles represent the assignment of the active jobs at
the beginning of the round; the dotted rectangle represents the assignment of the jobs that
arrive in the ith round and do not subsequently depart. (a) The algorithm's assignment.
(b) The adversary's assignment.
#n, arriving at
To generalize the procedure, note that the number of jobs that arrive in a given
round is chosen equal to the number of jobs that depart in the round preceding it.
Let us introduce some notation. Denote by r i the server to which requests are made
in the ith round and by f i the leftmost server to which any of these jobs gets assigned
by the algorithm. We have already chosen r
n, and we have seen
that
n. For the ith round of jobs,
suppose the following two conditions hold at the end of round i - 1 (see Figure 4).
1. In the adversary's assignment the active jobs are all assigned in the range
2. In the algorithm's assignment the active jobs that arrived in round
occupy servers f i-1 , . , r i , and no jobs are assigned to the left of f i-1 .
In the ith round, r i requests are made to server r i . They are assigned by the algorithm
in the range f i , . , f i-1 . Thus,
r i .
Next, r i+1 of these jobs depart, where r i+1 is chosen such that the r i -r i+1 remaining
jobs occupy servers f i , . , r i+1 . Thus, k(r equivalently,
f i-1 .
The actual lower bound construction follows. Let A be an on-line algorithm
purporting to be k-competitive for some k < 3. Without loss of generality, k is a
rational number arbitrarily close to 3. Consider the two sequences {# i } and {# i }
defined simultaneously below.
By substituting k
# i-1 for # i+1 in the second recurrence, we get
# i-1 .
It can be shown (see [6]) that there exists a minimal integer p such that # p < 0
and that # i and # i are rational for all i. The number of servers we use is n such that
are integers for . The recurrences
defining {# i } and {# i } hold for {f i } and {r i } as well. Let c be any positive integer;
we construct an input sequence of unit weight jobs such that
1. cr 1 jobs request server r 1 .
2. For
3. Of the cr i-1 jobs which have requested server r i-1 , the cr i jobs that
were assigned rightmost by A depart. (Ties are broken arbitrarily.)
4. cr i new jobs request server r i .
The lower bound proof proceeds as follows. (We omit the proofs for lack of space.)
For the input sequence to be well defined we must have r
13. For Figure 4).
Denote by J i the set of jobs requesting server r i and by J #
i the set of the cr i+1
jobs in J i that eventually depart. Let W (s, t) be the number of active jobs assigned
to the left of server s at time t and denote by t i the moment in time immediately
prior to the arrival of the jobs J i .
Observe that the recurrence f
r i+1 is equivalent to r
15. Suppose algorithm A is k-competitive. Then W (r
Corollary 16. Algorithm A is not k-competitive.
5. The tree hierarchy. In this section we study a generalization of the problem
in which the servers form a rooted tree. A job requesting some server t may be assigned
to any of t's ancestors in the tree.
Let us introduce some terminology. A server is said to be lower than its proper
ancestors. The trunk defined by a set of servers U is the set U # { s | s is an ancestor
of some server in U}. The servers eligible for a given job form a path which is also a
trunk. We refer to it interchangeably as the job's eligible path or eligible trunk.
For a given input sequence, denote by W T the total weight of jobs requesting
servers in trunk T , and let  {  T | T is a trunk}.
Denote by w max the maximum weight of a job in the sequence. Note the analogy with
the linear hierarchy. The following lemma can be proved in a manner similar to the
proof of the optimum lemma for the linear hierarchy (Lemma 1).
Lemma 17 (optimum lemma: tree hierarchy).
. In the fractional model,
. In the unweighted integral model,
. In the weighted integral model,
5.1. A doubling algorithm. The o#-line algorithm used in the proof of the
optimum lemma (Lemma 17) is nearly a valid on-line algorithm; its only o#-line feature
is the requirement that the value of H be known at the outset. Thus, employing
the standard doubling technique (see, e.g., [4]) we can easily construct an on-line algorithm
which is respectively 4-, 4-, and 7-competitive for the fractional, unweighted
integral, and weighted integral models. The algorithm we present here is based on the
more sophisticated doubling approach pioneered in [12]. It is 4-, 4-, and 5-competitive
in the respective cases. The randomized version of this algorithm is, respectively, e-,
e-, and (e
We start by describing the algorithm for the weighted integral model. The algorithm
uses two variables: GUESS holds the current estimate of H, and LIMIT deter-
LOAD BALANCING ON HIERARCHICAL SERVERS 545
mines the saturation threshold; a server is saturated if its load is at least LIMIT . We
say that a set of servers U is saturated if every server s # U is saturated. The set U is
overloaded if the total weight assigned to servers in U is greater than |U |  LIMIT . A
newly arrived job is dangerous if assigning it to its lowest unsaturated eligible server
will overload some trunk. In particular, if its eligible trunk is saturated, the job
is dangerous. The algorithm avoids overloading any trunk by incrementing LIMIT
whenever a dangerous job arrives. This, in turn, guarantees that whenever a job
arrives, at least one of its eligible servers is unsaturated. Note that assigning the job
may saturate the server to which it is assigned.
Algorithm Doubling
Initialize (upon arrival of the first job):
1. Let w be the first job's weight and T its eligible trunk.
2. GUESS w/|T |; LIMIT GUESS .
For each job:
3. While the job is dangerous:
4. GUESS 2  GUESS .
5. LIMIT LIMIT +GUESS .
6. Assign the job to its lowest unsaturated eligible server.
We divide the algorithm's execution into phases. A new phase begins whenever
lines 4-5 are executed. (The arrival of a heavy job may trigger a succession of several
empty phases.) Let p be the number of phases and denote by GUESS i and LIMIT i
the respective values of GUESS and LIMIT during the ith phase. For consistency
define Note that the initial value of GUESS ensures that GUESS 1 # H.
Proposition 18. If GUESS i # H for some i, then the ith phase is the last one.
Consequently, GUESS p < 2H.
Proof. Suppose GUESS i # H and consider the beginning of the ith phase. We
claim that from this moment onward, the algorithm will not encounter any dangerous
jobs. Suppose this is not true. Let us stop the algorithm when the first such dangerous
job is encountered and assign the job manually to its lowest unsaturated eligible server.
This overloads some trunk R. Let T be the maximal trunk containing R such that
T - R is saturated. Clearly, T is overloaded as well; the total weight assigned to it
is greater than |T |  LIMIT i . On the other hand, T was not overloaded at the end
of the (i - 1)st phase, since the algorithm never overloads a trunk. Thus, the total
weight of jobs assigned to T during the ith phase (including the job we have assigned
manually) is greater than |T |(LIMIT i - LIMIT i-1
maximality, all of these jobs must have requested servers in T . Thus, the total weight
of jobs requesting servers in T is greater than |T |H, yielding a contradiction.
Corollary 19. COST < 4OPT
Proof. The claim follows since COST < LIMIT
Thus, Algorithm Doubling is 4-competitive in the unweighted integral model and
5-competitive in the weighted integral model. In the fractional model we modify the
algorithm as follows. A job is called dangerous i# its eligible path is saturated. When
assigning the job we may have to split it, as in the proof of the optimum lemma for
the linear hierarchy (Lemma 1). This algorithm achieves COST # LIMIT p <
4OPT .
5.2. Randomized doubling. We consider randomization against oblivious ad-
versaries. The randomization technique we use is fairly standard by now; a similar
idea has been used several times in di#erent contexts (see, e.g., [11, 19, 15, 12, 10]).
The idea is to randomize the initial value of GUESS and to tweak the doubling pa-
rameter. Specifically, let r be a random variable uniformly distributed over (0, 1] and
select any constant k > 1. We replace lines 2 and 4 with
It can be shown that E (LIMIT (see [12] or [10] for details). This
expression is minimized at e  H by putting e. Thus, for e, the algorithm is
e-competitive in the fractional and unweighted integral models and (e+1)-competitive
in the weighted integral model.
5.3. Lower bounds for temporary jobs. In contrast to the linear hierarchy,
allowing temporary jobs in the tree hierarchy has a drastic e#ect on the competitiveness
of the solutions. For the unweighted integral model, we show deterministic and
randomized lower bounds of # n and 1(1 1), respectively. These bounds are
tight, up to a multiplicative constant, as demonstrated by the upper bound shown
in [6] for the general problem with unrestricted eligibility constraints. Our randomized
lower bound construction applies in the fractional model as well.
5.3.1. A deterministic lower bound for the integral models. Let A be a
deterministic on-line algorithm, and let 1. We show an
input sequence for which A's assignment satisfies COST # k
The server tree we use has a flower-like structure. It is composed of a stem and
petals. The stem consists of k servers s 1 , s 2 , . , s is the root, and s i is the parent
of s 1. The petals, are all children of s k . Server
s k is called the calyx.
Suppose that the competitiveness of A is better than k for the given n. Consider
the following request sequence. Let c be an arbitrarily large integer.
1. For
2. jobs, each of unit weight, request the petal p i .
3. Of these jobs, ck now depart. (The rest are permanent.) The choice of
which jobs depart is made so as to maximize the number of jobs assigned
by A to p i which depart.
4. ck jobs request the calyx.
During the first stage (lines 1-3), the adversary always assigns the permanent
jobs to the petal and the temporary ones to the servers in the stem, c jobs to each
server. Thus, at the beginning of the second stage, no jobs are assigned to the stem
servers, and the adversary assigns c new jobs to each of them. Thus,
Consider the jobs requesting p i . Since A is better than k-competitive, it assigns
fewer than ck jobs to p i . Thus, in each iteration more than c permanent jobs are
assigned by A to servers in the stem. Hence, at the beginning of the second stage
there are more than c(k 2
jobs assigned to servers in the stem. Since the additional
ck jobs must be assigned to servers in the stem, at least one server must end up
with a load greater than ck, contradicting the assumption that A is better than k-
competitive.
LOAD BALANCING ON HIERARCHICAL SERVERS 547
5.3.2. A randomized lower bound. Let us generalize the previous construc-
tion. We use a flower-like server tree with p petals and a stem of s servers
As before, the input sequence has two stages. The first consists of p iterations, where
in the ith iteration, c  request the petal p i and then c  s of them depart.
In the second stage cs jobs request the calyx. The goal in the first stage is to "push"
enough jobs into the stem so that the algorithm will fail in the second stage.
Consider the ith iteration. Let X j be the random variable denoting the contribution
of the jth job to the load on servers in the stem. (In the integral model
this is a 0-1 variable; in the fractional model X j may assume any value between 0
and 1.) Since the algorithm is better than k-competitive, the expected total weight
assigned to p i is less than ck, so E( # j k). Thus, there exist c jobs
c such that
c(s+1-k)/(s+1). The adversary makes these
jobs permanent and terminates the rest.
Consequently, at the beginning of the second stage the expected total load on
the servers in the stem is greater than cp(s 1), and at the end of the
second stage the expectation grows to more than cs
the algorithm is better than k-competitive, the expected maximum load on a server
in the stem must be less than ck, and thus the expected total load on servers in the
stem must be less than cks. To reach a contradiction we choose s and p to satisfy
Solving the equation yields
ks 2
Minimizing n (for fixed subject to the last equation yields
6. Other eligibility restrictions. In the hierarchical servers problem the sets
of eligible servers for a job have a restricted form. For example, in the linear hierarchy
they have the following form: all servers to the left of some server s. This is a special
case of the problem considered in [7], where eligible sets may be arbitrary. In this
section we study various other restrictions on the eligible sets. We focus on the
following three.
1. The servers form a path and the set of servers eligible for a given job must
be contiguous on the path.
2. The servers form a rooted tree and each job specifies a node v, all of whose
descendents (including v itself) are eligible.
3. The number of servers eligible for any given job is at most k for some fixed
We show how to extend
the# log n) lower bound of [7] to these three variants
of the problem. This shows that the greedy algorithm, which is O(log n)-competitive
for the general problem, remains optimal (up to a multiplicative constant) in many
restrictive scenarios.
For the first variant, consider the following input sequence. For convenience
assume n is a power of 2 (otherwise consider only the first 2 #log n# servers on the
path). All jobs have unit weight, and they arrive in log n rounds. The ith round
consists of m all of which specify the same set of eligible servers S i . The
sets S i are chosen such that |S i In the first round all servers are eligible.
548 AMOTZ BAR-NOY, ARI FREUND, AND JOSEPH (SEFFI) NAOR
Having defined S i , we construct S i+1 as follows. Suppose the total weight assigned
to servers in S i at the end of the ith round is at least ni/2 i (as is certainly the case
1). The set S i is contiguous, i.e., its servers form a path. At least half of the
total weight assigned to S i is assigned to either the first half of this path or to its
second half. We define S i+1 as the half to which the majority of the weight is assigned
(breaking ties arbitrarily). Thus, the total weight assigned to S i+1 at the end of the
1)st round is at least n/2 We define S log n+1 in the
same manner and call the single server which it comprises the leader. The load on the
leader at the end of the last round is at least 1log n. The adversary assigns the jobs
in the ith round to the servers S i - S i+1 , one job to each server. Thus, OPT # 1,
and the lower bound follows.
For the second variant we use a very similar construction. The servers are arranged
in a complete binary tree. The number of jobs in the ith round is defined by
the recurrence m
1). The sets of eligible servers
are defined as follows. In the first round all servers are eligible. Let v i be the root of
the subtree S i ; we define S i+1 as the subtree rooted at the child of v i to which more
weight is assigned at the end of the ith round.
For the third variant we use a recursive construction. Partition the servers into
n/k subsets of k servers each and apply the construction of the first variant to each
subset. The load on the leader of each subset is now # log k). Continue recursively
on the set of leaders. Each level of the recursion increases the load on the leaders
in that level by # log k), and there are #(log k n) = #(log n/ log levels. Thus,
log n). At each level of the recursion, the adversary assigns no weight to
the leaders and at most one job to the other servers. Hence, OPT # 1, and the lower
bound follows.



--R

Handbook of Mathematical Functions
Better bounds for online scheduling




The competitiveness of on-line assignments
New algorithms for an ancient scheduling problem
A better lower bound for on-line scheduling
New algorithms for related machines with temporary jobs
Yet more on the linear search problem


A lower bound for on-line scheduling on uniformly related machines
An improved approximation ratio for the minimum latency problem
Bounds for certain multiprocessor anomalies
A better algorithm for an ancient scheduling problem
Online resource minimization


--TR

--CTR
Pilu Crescenzi , Giorgio Gambosi , Gaia Nicosia , Paolo Penna , Walter Unger, On-line load balancing made simple: Greedy strikes back, Journal of Discrete Algorithms, v.5 n.1, p.162-175, March, 2007
On-line algorithms for the channel assignment problem in cellular networks, Discrete Applied Mathematics, v.137 n.3, p.237-266, 15 March 2004
hierarchical servers;temporary jobs;load balancing;resource procurement;on-line algorithms