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: ea
ch 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 hi
erarchy. Each job carries a certain load, which it imparts to the server it
is assigned to. The goal is to nd a competitive assignment in which the ma
ximum total load on a server is minimized.
We consider the linear hierarchy in which the servers are totally ordered i
n terms of their capabilities. We investigate several variants of the probl
em. 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 assi
gned to several servers, each receiving some fraction of its weight. Finall
y, temporary ( as opposed to permanent) jobs may depart after being active
for some finite duration of time. We show an optimal e-competitive algorith
m for the unweighted integral permanent model. The same algorithm is (e+1)-
competitive in the weighted case. Its fractional version is e-competitive e
ven if temporary jobs are allowed. or the integral model with temporary job
s 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 unweig
hted case ( both integral and fractional). This bound is valid even with re
spect to randomized algorithms. We also show a lower bound of 3 for the unw
eighted integral model when temporary jobs are allowed.
We generalize the problem and consider hierarchies in which the servers for
m a tree. In the tree hierarchy, any job assignable to a node is also assig
nable 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 (n) lower
bound when temporary jobs are allowed.