On-line Resource Management with Application

to Routing and Scheduling 

Stefano Leonardi y Alberto Marchetti-Spaccamelay

Abstract
We propose a framework to model on-line resource management problems based
on an on-line version of positive linear programming. We consider both min cost
problems and max benet problems and propose logarithmic competitive algorithms
that are optimal up to a constant factor.
The proposed framework provides a general methodology that applies to a wide
class of on-line problems: shop scheduling, packet routing, and in general a class
of packing and assignment problems. Previously studied problems as on-line multi-
processor scheduling and on-line virtual circuit routing can also be modeled within
this framework.

Keywords: on-line algorithms, competitive analysis, routing, scheduling, linear program-

ming.

 A preliminary version of this paper appears in the Proceedings of the 22nd International Colloquium
on Automata, Languages, and Programming, LNCS 944, Springer-Verlag, 1995. This work was partly
supported by EC ESPRIT BRA Alcom II under contract No.7141,EC HCM project Map and by Italian
Ministry of Scientic Research Project 40% \Ecienza di Algoritmi e Progetto di Strutture Informative".
y Dipartimento di Informatica e Sistemistica, Universit
a di Roma \La Sapienza",via Salaria 113, 00198-
Roma, Italia. e-mail: fleon,marchettig@[Link]
1 Introduction
In this paper, we consider on-line resource management problems, on-line optimization
problems concerned with the ecient use of resources to accomplish a set of tasks {
also called jobs in the following. Informally, an on-line resource management problem is
dened by a sequence of jobs that are presented one at a time. The processing of a job
can be done following one of a set of possible alternatives. Dierent alternatives make use
of dierent set of resources. Decisions about how to process a job must be taken when
the job is presented, without knowledge of the jobs that will follow in the sequence.
This class of problems includes routing, scheduling and nancial problems. The ap-
plication elds we consider give rise to both cost problems and benet problems. In a cost
problem every job can be accomplished in several ways. The goal of the on-line algorithm
is to minimize the amount of resources necessary to deal with all the jobs in a sequence.
In a benet problem the amount of resources available is xed at the beginning and a
revenue is obtained for each accepted job. The goal is to maximize the benet gained
over a sequence of jobs without exceeding the available resources. Within this goal, a job
is possibly not served at all.
We will present a framework based on an on-line version of positive linear programming
to model on-line resource management problems.
Competitive analysis. We use competitive analysis [16, 20, 19, 24, 30] for the analysis
of on-line algorithms; competitive analysis compares an on-line algorithm with an o-line
adversary, that has complete knowledge of the input instance and computes an optimal
solution.
Namely, an algorithm for an on-line cost problem is -competitive if for all the input
sequences, the cost associated with the algorithm is no more than  times the cost associ-
ated with the optimal o-line algorithm, up to an additive constant factor. Similarly, an
algorithm for an on-line benet problem is -competitive if for all the input sequences, the
benet obtained by the algorithm is no less than 1= the benet obtained by the optimal
o-line algorithm, up to an additive constant factor. If the additive constant is zero then
the algorithm is said to be strictly competitive. For on-line randomized algorithms, we
measure the expected cost or benet of the algorithm, where the expectation is over the
random choices of the algorithm. We compare a randomized on-line algorithm with an
oblivious adversary [10], an adversary that knows the algorithm but does not know the
outcome of the random choices of the algorithm.
We are interested in determining the exact competitive ratio of an on-line problem.
1
An on-line problem is said to be -competitive if there exists an on-line -competitive
algorithm for the problem, and no algorithm can be 0-competitive with 0 < . We also
say in this case that  is a lower bound over the competitive ratio.
Previous work. The on-line version of a positive linear programming problem that we
study in this paper models fractional and integer packing problems. This class of problems
has been extensively studied in its o-line version (see for example [26, 27]).
Previous work on on-line problems related to those considered in this paper mainly
regards multiprocessor scheduling, routing and nancial problems.
Scheduling. Several variants of scheduling problems are commonly studied. For instance,
in multiprocessor scheduling, machines can be identical, uniformly related, if the speed of
a machine does not depend upon the currently assigned job, or unrelated, if every machine
has a particular speed for any job [22]. Every job can be associated with an arrival time
and/or a limited duration. Moreover, the parameters that dene each job can be either
known or unknown.
Shmoys, Wein and Williamson [29] consider the problem of minimizing the completion
time to process a set of jobs, assuming that the arrival and/or the processing time of each
job are not known. If the arrival times are not known, a technique that solves the problem
at the expenses of a factor of 2 in the competitive ratio is proposed. If the processing times
are not known, the List Scheduling algorithm proposed by Graham [17] is shown by the
authors to be optimal for identical machines; in the case of uniformly related machines, an
optimal O(log m)-competitive algorithm, where m is the number of machines, is presented.
Aspnes et al. [1] study load balancing for uniformly related and unrelated machines,
devising a constant competitive algorithm for the rst case, and an optimal O(log m)-
competitive algorithm for the second case. A particular instance of the problem for
unrelated machines is the on-line assignment problem, in which every job can be assigned
only to a subset of the m available processors; an
(log m) lower bound on the competitive
ratio is obtained for this case by Azar, Naor and Rom [9]. The problem becomes harder if
the processing time of the jobs is not known until their execution is terminated, while jobs
p
must be scheduled immediately at their arrival time. For this problem an
( m) lower
bound is proved by Azar, Broder and Karlin [6] for randomized algorithms. If durations
are limited but known, a logarithmic competitive ratio is still possible with a deterministic
algorithm [7].
Routing. Work in on-line routing problems mainly regards admission control and virtual

2
circuit routing in communication networks. In virtual circuit routing two nodes of the
network that wish to exchange a message establish a xed connection on a path of the
network { called virtual circuit { and route every packet of the message on this path. The
use of virtual circuits is particular important in high speed networks (e.g. ATM) and in
real time applications such as video and voice transmission. Each communication request,
commonly named call, asks for the establishment of a virtual circuit between two points
in the network, at a certain transmission rate and for a certain duration.
Aspnes et al. [1] consider a cost version of the problem, where all calls must be
accepted and the goal is to minimize the maximum load on links; they propose a O(log n)
competitive algorithm, where n indicates the number of nodes in the network. Further
work on the load version of the problem appears in [7].
In the benet or throughput version of the problem, calls can be either accepted or
rejected and a specic benet is accrued for each accepted call. The constraint is to
maintain the sum of the transmission rates of the calls assigned on a virtual circuit that
crosses a given link below the available bandwidth on that link. This problem is also called
the call control problem. Deterministic algorithms with logarithmic competitive ratio
have been proposed by Awerbuch, Azar and Plotkin [3] if any call cannot ask more than
a logarithmic fraction of the bandwidth available on any link. Without this restriction
the problem becomes much harder and deterministic algorithms can obtain only a very
poor competitive ratio.
Awerbuch et al. [5] concentrate on networks with links of uniform capacity. A rst
simplication is to get ride of the fact that calls can have dierent benet, duration
and transmission rate. The uctuation of these values can be dealt with by randomized
algorithms at the expenses of a O(log
) multiplicative factor in the competitive ratio,
where
is the ratio between the maximum and the minimum value of a single parameter.
Lipton and Tomkins [23] show that this factor increases to O(log1+
), for any  > 0, if
the value of
is not known in advance. The results for dierent benets and durations
extend to networks with links of varying capacity. A similar result is not known for the
case of dierent transmission rates and varying link capacities.
The simplied problem in which we assume transmission rate equal to the bandwidth
of the links, equal benet and innite duration is the on-line version of the well known
edge-disjoint paths problem. Given a graph, a sequence of pairs of vertices are presented
one by one to the algorithm. The goal is to select a set of pairs of maximum cardinality
that can be connected with edge-disjoint paths. Randomized algorithms with logarithmic

3
competitive ratio have been proposed for specic topologies such as trees [5, 8], meshes
[8, 21], and a particular class of planar graphs [21]. For general networks, Bartal, Fiat
and Leonardi [11] show an
(n ) lower bound on the competitive ratio of randomized
algorithms even if preemption { the possibility of discarding already accepted calls { is
allowed.
Financial problems. We nally mention previous work on nancial problems. Resource
management problems have often a straightforward economic interpretation. For instance,
in the call control problem, a network manager has to allocate resources in order to
maximize the economic revenue from customers that ask for network services.
A few on-line nancial problems have been recently studied. In the currency exchange
problem [12] a given amount of a rst currency is available at the beginning of a trading
period. Each time a new exchange rate is announced, an algorithm has to decide how
much to convert to a second currency. The goal is to obtain the maximum amount of
the second currency at the end of the trading period. We also mention the mortgage
problem [13], where a uctuating mortgage rate and associated xed re-nancing charges
lead to the question \re-nance or not?" The goal is to minimize the overall interest and
re-nancing cost.

1.1 Results of this paper

In this work we propose a general methodology based on positive linear programming to
deal with a wide variety of on-line resource management problems both for their cost and
the benet version. Moreover, we extend the model to jobs arriving over time and leaving
the system within a given deadline. Finally, we present several applications to routing,
scheduling and nancial problems, some of which have not previously been studied.
Benet Problems. In Section 2 we present the methodology for benet problems,
both for real and integer variables. We model the benet version of a resource manage-
ment problem as a linear programming problem where the objective function has to be
maximized and constraints are inequalities that bound the amount of available resources.
The coecients of the jobs are known for one job at a time and the value of the variables
must be determined before the next variable is disclosed.
Some problems that can be modeled with this framework have already been studied.
For instance the unidirectional currency exchange problem [12] is modeled as a benet
problem with a single constraint. The throughput version of the on-line virtual circuit
routing problem [1, 3] is modeled using a constraint for each link of the network. For each
4
call a dierent alternative is associated with each possible virtual circuit that connects
the two nodes of the network. The coecients of an alternative are equal to the required
bandwidth on any link, that is equal to transmission rate for the links of the virtual
circuit, 0 otherwise.
For real variables, we obtain optimal algorithms with logarithmic competitive ratio.
For integer variables, we present optimal algorithms with logarithmic competitive ratio if
any job cannot require more than a logarithmic fraction of any single resource.
The above results are obtained extending the techniques developed for the on-line
virtual circuit routing problem [3] (see also the unidirectional exchange problem [12])
to a more general framework. The idea is to associate a cost with each resource, that
is exponential in the fraction of that resource that has already been assigned; the job is
accepted if there is an alternative that uses a set of resources with total cost less than the
benet obtained by accepting the job for processing.
The cost function we use allows to extend the previous known results to a more general
class of problems. The obtained results are not worse than the already known bounds
for specic problems; in some cases the known bounds are also improved by a constant
factor ( e.g. the competitive ratio for the virtual circuit routing problem is improved by
a factor of 2).
A further contribution of this paper is to show in both the integer and the real case a
2-competitive algorithm when the on-line algorithm has more resources than the optimal
o-line adversary by a multiplicative logarithmic factor. This result holds for all the above
mentioned specic problems.
Cost Problems. In the cost version of on-line resource management (see Section 3),
all jobs have to be accepted for processing. Every job can be processed by choosing one
possibility in a set of dierent alternatives. Each alternative uses a specic amount of
each resource and the goal is load balancing, i.e. to minimize the maximum amount of a
single resource necessary to handle all the jobs in the sequence.
Previously studied problems of this kind are the load balancing version of virtual
circuit routing and parallel machine scheduling on unrelated machines [1]. Also for cost
problems we extend the techniques of [1] to a more general positive linear programming
problem.
The methodology for benet and cost problems is also extended to jobs that have
limited execution (see Section 4), i.e. jobs that enter the system at a certain time and
leave the system before a known individual deadline. This is done at the expenses of a

5
logarithmic additive term in the competitive ratio.
Applications. The proposed methodology nds many applications. Applications to
nancial problems, virtual circuit routing and load balancing have already been mentioned
before.
In the following we discuss problems for which, to the best of our knowledge, no
previous on-line result was known. In shop scheduling problems [28] (see Section 5.1), a
job is specied by an arrival time, a deadline and a set of non-overlapping operations to
be performed according to some precedence rules, represented by a partial order; every
operation has to be performed on a specic kind of machine, requires a given processing
time, and once started cannot be preempted. In the benet version, a benet is accrued
if all the operations associated with a job are completed within the deadline. In the cost
version, the goal is to minimize over all the machines the maximum processing power of
every single machine necessary to terminate all the jobs within the deadline.
The running time of the algorithm that processes each job is polynomial in the number
of machines and in the maximum time available to nish a job for job-shop scheduling,
where the partial order is a linear order, non-polynomial for ow-shop scheduling, where
the partial order is arbitrary.
Packet routing (see Section 5.2) is the second application; in this case we assume that
packets are independently routed, i.e. every packet follows a proper route through the
network. In the cost version every packet enters the system at a certain time and must be
delivered to its destination within a maximum individual deadline; we are interested in
minimizing the maximum bandwidth required on the network links to route the packets
injected in the network. In the benet version, the bandwidth on every link is xed and
the goal is to maximize the number of packets that can be delivered at their destinations.
On-line packet routing has also been later considered in [2].
Other on-line problems that are naturally modeled within this framework are the
fractional and integer version of packing problems [26, 27], knapsack and assignment
problems.

2 A methodology for on-line benet problems

An on-line resource management benet problem is dened by a set of m distinct resources.
Resource i can be assigned for a maximum amount ai . A sequence of n jobs is presented
to the algorithm. Job j has benet per unit bj and can be scheduled with kj dierent
alternatives. The r-th alternative for job j is dened by m values arij ; i = 1; : : : ; m; arij is
6
a non negative real number indicating the amount of resource i necessary to schedule job
j with alternative r.
A variable xrj is associated with the r-th alternative for job j . The values of the
variables xrj must be assigned before the future jobs in the sequence are presented. The
goal is to maximize the benet accrued over the sequence of jobs without exceeding the
use of the resources. The o-line version of the problem is formalized as follows:

max
Xn b Xkj
xrj
j
j =1 r=1

subject to
Xn X
kj
ar xr  a ; i = 1; : : : ; m
ij j i
j =1 r=1

0
X xr  1; j = 1; : : : ; n
kj
j
r=1
We rst study the problem in which the variables xrj have real values in [0; 1], after-
wards the f0; 1g integer case. We abuse notation by denoting with xrj both the variable
and its value. Furthermore, if not specied otherwise, the base of logarithms is 2.

2.1 Upper bounds for real variables

In this section we consider the case of real variables, namely xrj 2 [0; 1] for any alternative
associated with a job. Since every job can be globally scheduled for at most 1 unit, xrj
indicates the percentage of job j scheduled with the r-th alternative.
The competitive ratio will depend on the values of m, bj and arij . We assume that the
benet of a job has value in the range [1; B ], with B  1, and that, for every non-zero
coecient arij , the ratio arij =ai is in the range [1/P,1], with P  1. The algorithm is easily
generalized when B and P denote the corresponding ratios between the maximum and
the minimum values. In the following we assume that values P and B are known to the
algorithm.
Let i = a1i Pkj =11 Pkr=1
j
arij xrj be the fraction of resource i currently assigned when
the j -th job of the sequence is presented. The algorithm associates with every resource
an exponential function of the current assigned fraction; namely, let  = 2mPB , and
ci = m1 i be the current cost of resource i. We dene C r = Pmi=1 aaiji ci as the global cost
r

of alternative r for job j .

The algorithm schedules job j with alternative r only if the oered benet bj is not
less than the global cost of the alternative. It means that the required benet to \sell"

7
resources grows exponentially with their current assigned fraction. This is to model that
the scarcer resources are, because they have been assigned to previous jobs, the more
precious they become.
Informally, when job j is presented the algorithm initially assigns xrj := 0; r =
1; : : : ; kj , and computes the global cost associated with every alternative. The basic
step of the algorithm is as follows:
 Schedule job j for a percentage at most log1  with one alternative r of minimum
global cost C r , if C r  bj and Pkr=1
j
xrj < 1.
Every time an alternative for job j is selected, the assigned fraction and hence the cost
of the assigned resources increases. The basic step is repeated until all alternatives have
global cost greater than bj or the job is globally assigned for a value equal to 1. Therefore,
at the end of the iteration, job j will be scheduled with a possibly empty sequence of sj
alternatives r(1); : : : ; r(sj ), with fractions x1j ; : : : ; xsjj , respectively.
Formally, the values of variables xrj associated with job j are assigned with the following
algorithm, where i, i = 1; : : : ; m is the current assigned fraction of resource i:
xrj := 0, r = 1; : : : ; kj
l := 1
Let r(l) be one of the alternatives with minimum global cost C r(l)
while C r(l)  bj and r=1
Pkj xr < 1 do
xlj = min(1 Pkr=1
j
j
xrj ; log1  )
xjr(l) := xjr(l) + xlj
r(l)
i := i + aijai x
l := l + 1
Let r(l) be one of the alternatives with minimum global cost C r(l)
endwhile

Observe that an alternative may be selected more times during the while loop.
First we prove that the algorithm gives a feasible solution, i.e. no resource i is assigned
for more than ai.
Lemma 2.1 The solution given by the algorithm is feasible.
Proof. Assume that the solution becomes unfeasible after having scheduled job j with
alternative r, exceeding the use of resource i.
8
 Any alternative is selected with a percentage x  log1  . Since the requirement of
resource i is greater than ai after alternative r is selected, it follows that the assigned
fraction before choosing alternative r is:
arij
i > 1 a x  1 log1  :
i
Therefore, the global cost of alternative r would have been at least
arij arij i 1 1 1 1  =Bb ;
ai i mai  > mP 
c = = mP
log  j
2
thus yielding a contradiction. 2
Denote with xrj and xj r ,r = 1; : : : ; kj , the fraction of job j globally scheduled with
alternative r by the on-line algorithm and by the optimal o-line algorithm, respectively.
Let Q be the set of jobs for which the on-line algorithm has set all the variables to 0. Let
A = A0 [A00 be the set of jobs for which the on-line algorithm has set at least one variable
to a non-zero positive value. In particular, for any j 2 A0 it holds Pkr=1 j
xrj < 1, while
for every j 2 A00 it holds Pkr=1
j
xrj = 1. Let r(1); : : : ; r(sj ) be the sequence of alternatives
chosen by the algorithm for job j . Let ci(l + 1; j ) be the cost of resource i after job
j has been scheduled with alternative r(l) for a fraction xlj , where 0 < xlj  log1  . Let
ci(j +1) = ci(j; sj +1) be the cost of resource i at the end of the schedule of job j . Finally,
let ci(n + 1) be the cost associated with the i-th resource at the end of the sequence of n
jobs.
Lemma 2.2 Pj2Q[A0 bj Pkr=1
j
xj r < Pmi=1 ci(n + 1).
Proof.r For any job j with j 2 Q[A0 and for any alternative r it holds bj < Pmi=1 aaiji ci 
r

Pm aij
i=1 ai ci (n + 1).
Then, the benet obtained by the o-line algorithm on the set of jobs
Q [ A0 is given by:
X bX kj
 r
xj <
X X
kj X
m ar
xj r aij ci(n + 1)
j
0
j 2Q[A r=1 0 j 2Q[A r=1 i i=1

X
m
= ci(n + 1)
X X ij xr  X c (n + 1);
kj ar m
i
i=1 0 ai j
j 2Q[A r=1 i=1
where the last inequality follows from the feasibility of the optimal solution.
2

9
Lemma 2.3 Pmi=1 ci(n + 1)  1 + log  Pj2A bj Psl=1
j
xlj .
Proof. It is sucient to prove that for every j 2 A and l = 1; : : : ; sj , Pmi=1[ci(j; l + 1)
ci(j; l)]  xlj bj log . In fact,
XX sj X m
[ci (j; l + 1) ci(j; l)] =
X m XX sj
[ci (j; l + 1) ci(j; l)] =
j 2A l=1 i =1 i =1 j 2A l=1
Xm Xm
[c (n + 1) c (1)] = [c (n + 1) 1 ];
i i i
i=1 i=1 m
where c (1) = 1 is the cost of resource i when the rst job is presented, thus yielding
Pm ci(n +i 1)  1m+ log  P bj Psj xl .
i=1 j 2A l=1 j
In the following i is the assigned fraction of resource i when alternative r(l) for job
j is selected. Now, observe that
ar(l) i arij(l) xl log 
1
ci(j; l + 1) ci (j; l)  m ( i + ijai xlj 
i ) = m (2 ai j 1):
Since 2x 1  x, if 0  x  1, we obtain
aijr(l) i l aijr(l)
ci(j; l + 1) ci(j; l)  xj log  a m  = xj log  a ci(j; l):
l
i i
Summing for every constraint, we get
Xm
[ci (j; l + 1) ci(j; l)]  xj log 
l Xm ar(l)
ij c (j; l)  b xl log :
i j j
i=1 i=1 ai
2
Theorem 2.4 The algorithm for on-line resource management benet problems with real
variables is (1 + log )-competitive.
Proof. Denote with ON and OPT the benet obtained by the on-line algorithm and by
the optimal o-line algorithm, respectively.
The benet achieved by the on-line algorithm is Pj2A bj Psl=1
j
xlj . Lemmas 2.2 and
2.3 imply that the o-line benet over the set Q [ A0 is Pj2Q[A0 bj Pkr=1 j
xj r < 1 +
log  Pj2A bj Psl=1
j
xlj . Since Pkr=1
j
xrj = 1, j 2 A00,
OPT =
X X
kj

bj xj +r X X
kj
bj xj r
j 2Q[A0 r=1 j 2A00 r=1
X Xsj
< 1 + log  bj xlj +
X b  1 + ON log  + ON
j
j 2A l=1 00j 2A
= 1 + (1 + log )ON:
2

10
2.2 Lower bounds for real variables
In this section we show that the algorithm of the previous section is almost tight by
proving that randomized algorithms do not allow better bounds up to a constant factor.
The proofs of the theorems of this section are along the same lines of the lower bound
proofs of [3] for the virtual circuit routing problem.
Theorem 2.5 Any deterministic or randomized algorithm for on-line resource manage-
ment benet problems with real variables has competitive ratio
(log m), where m is the
number of resources.
Proof. We rst give the proof for deterministic algorithms. We assume that the benet
of every job is 1, that for every resource i = 1; : : : ; m, ai = 1, that only one alternative is
possible for every job, with coecients aij 2 f0; 1g.
Assume that m is a power of 2. We consider a sequence of (log m + 1) groups of jobs.
Group j; j = 0; : : : ; log m, contains 2j jobs, every job requiring m2 j distinct resources.
Namely, for job jk ; k = 1; : : : ; 2j , aijk = 1; i = (k 1)m2 j + 1; : : : ; km2 j , 0 otherwise.
For any on-line algorithm, let us dene with zj the benet obtained from group j of
jobs, and let j be the ratio between the optimal and the on-line benet after that the
jobs of group j have been presented. Every unit of benet from group j requires the
assignment of m2 j resources. Clearly, the global amount of assigned resources cannot
exceed m and thus Plog j =0 zj 2  1. Since the optimal o-line benet when the j -th
m j
group has been presented is 2j , it holds:
X
log m 1 = logXm 2 j X j
z =
Xm z logXm 2 j  2 logXm z 2 l  2:
log
l l l
j =0 j j =0 l=0 l=0 j =l l=0
Then, there exists at least an index j such that 1=j  log2m ; the sequence is stopped
after that group j is presented.
The proof for randomized algorithms is obtained by replacing any variable zj with its
expected value E (zj ). Clearly, the expected benet of the on-line algorithm is given by
the sum of the expected benets for any group of jobs in the sequence. Moreover, for any
outcome of the coin tosses, the values assigned to the variables zj , j = 0; : : : ; log m, are
conditioned to satisfy the relation Plogj =0 zj 2  1. Then, for the linearity of expectation,
m j
we can also state Plog
j =0 E (zj )2  1. Now the proof for randomized algorithms continues
m j
along the same lines of the proof for deterministic algorithms. 2

11
 The following two theorems state a lower bound on the competitive ratio of both
randomized and deterministic algorithms as function of B , maximum benet, and P , the
maximum fraction of a single resource required by an alternative associated with a job.
Theorem 2.6 Any deterministic or randomized algorithm for on-line resource manage-
ment benet problems with real variables has competitive ratio
(log B ).
Proof. It is sucient to consider only one resource with a1 = 1 and B equal to a power of
2. The instance is formed by a sequence of log B +1 jobs, that can be scheduled with only
one alternative specied by a1j = 1, j = 0; : : : ; log B . The benet bj of the j -th job in the
sequence is exponentially growing, namely the j -th job of the sequence, j = 0; : : : ; log B ,
oers benet bj = 2j .
For any on-line algorithm, let zj be the benet gained by the algorithm for job j .
Clearly, Plog
j =0 zj 2  1, since the only available resource cannot be assigned for more
B j
than one unit. Let j be the ratio between the optimal and the on-line benet after job
j is presented. We have:
X
log B 1 = logXB 2 j Xj
z =
XB z logXm 2 j  2 logXB z 2 l  2:
log
l l l
j =0 j j =0 l=0 l=0 j =l l=0
Thus, there exists a value j such that j  log2 m , and the sequence is stopped after that
job j is presented. The proof for randomized algorithms is similar to the proof of theorem
2.5. 2
The proof of the following theorem is similar to the proof of Theorem 2.6. For this
reason we limit to a sketch of the proof.
Theorem 2.7 Any deterministic or randomized algorithm for on-line resource manage-
ment benet problems with real variables has competitive ratio
(log P ).
Proof. It is sucient to consider only one resource with a1 = 1, P equal to a power of 2,
and a sequence of log P + 1 jobs, with benet bj = 1, having only one alternative with
coecient a1j = 2(logPP j) , j = 0; : : : ; log P . The sequel of the proof is similar to the proof
of Theorem 2.6. 2

2.3 Upper bounds for integer variables

In this section we propose an algorithm for on-line resource management benet problems
with integer variables, namely xrj 2 f0; 1g for every alternative associated with job j .
Therefore, every job can be either accepted with one alternative or rejected.
12
 We pose the following restriction on the maximum amount of a single resource that
can be asked from any alternative to schedule a job:
arij 1

ai log  (1)
A logarithmic upper bound is also obtained for integer variables under restriction
1, using a simpler algorithm. We use the terminology of the previous subsection. The
algorithm for job j is as follows:
xrj := 0, r = 1; : : : ; kj
Let l be one of the alternatives with minimum global cost C l
If C l  bj then xlj := 1

Note that this algorithm is the same algorithm proposed in [3] for virtual circuit
routing, where we use a slightly dierent weight function. The analysis of the algorithm
has the same structure of the proof of Theorem 2.4.
In order to prove the feasibility of the solution, observe that under restriction (1),
i, the assigned fraction of resource i, increases at most by log1  . Then, Lemma 2.1 can
be easily adapted to prove that the solution given by the on-line algorithm for integer
variables is feasible. Let A be the set of accepted jobs, i.e. one variable has been assigned
to 1. Let Q be the set of rejected jobs for which all the variables have been set to zero
by the on-line algorithm.
The next lemma gives a rst lower bound on the benet achieved by the optimal
o-line algorithm. The proof is analogous to the proof of Lemma 2.2 and hence it is
omitted.
Lemma 2.8 Pj2Q bj Pkr=1 j
xj r < Pmi=1 ci(n + 1).
Lemma 2.9 Pmi=1 ci(n + 1)  1 + log  Pj2A bj .
Proof. Let ci(j + 1) be the cost of resource i after job j has been presented. Similarly
to the proof of lemma 2.3, it is sucient to prove that Pmi=1[ci(j + 1) ci (j )]  bj log ,
for every j 2 A. Let l be the alternative chosen for job j 2 A, and let i be the current
assigned fraction of resource i before job j is scheduled. First observe that
1
ci(j + 1) ci(j ) = m (
ar
i + aiji   i log  arij
 ) = m (2 ai 1):
i

Since 2x 1  x, if 0  x  1, it follows that

ar ar
ci(j + 1) ci(j )  log  a ijm i = log  aij ci(j ):
i i

13
 Then we get:
X
m X
m ar
[ci(j + 1) ci(j )]  log  aij ci(j )  bj log :
i=1 i
i=1
2

Theorem 2.10 The algorithm for on-line resource management benet problems with
integer variables under restriction (1) is (1 + log )-competitive.
Proof. Denote with ON and OPT the benet obtained by the on-line algorithm and
by the optimal o-line algorithm, respectively. For every j 2 A there is one alternative
r 2 f1; : : : ; kj g, for which xrj = 1. Then ON = Pj2A bj . From lemma 2.8 and from
lemma 2.9 it follows that Pj2Q bj Pkr=1
j
xj r < 1 + log  Pj2A bj . The benet obtained by
the optimal o-line algorithm is
X X
kj X X
kj X
OPT = bj xj + bj xj r  1 + (1 + log ) bj = 1 + (1 + log )ON:
 r
j 2Q r=1 j 2A r=1 j 2A
2
In the remaining part of this section we consider the case in which the on-line algorithm
has more resources than the adversary by a logarithmic factor; the size of the i-th resource
is ai log  for the on-line algorithm, while it is ai for the o-line algorithm. Clearly,
restriction (1) is no more necessary. We show that the algorithm for integer variables has
a constant competitive ratio. (The same result can be derived for real variables.)
The solution provided by the algorithm is clearly feasible since the assigned fraction
of any resource increases at most by log1  when a new job is accepted by the on-line
algorithm. Lemma 2.8 holds without any change, while we can state the following lemma.
Lemma 2.11 Pmi=1 ci(n + 1)  1 + Pj2A bj .
Proof. We use the terminology of the proof of Lemma 2.3. As in that case it is sucient
to prove that for any j 2 A Pmi=1 [ci(j + 1) ci(j )]  bj .
To prove the claim, rst observe that
ci(j + 1) ci(j ) = m1 (i+ ai log  i ) = m (2 ai
arij i arij
1):
Since 2x 1  x, if 0  x  1, it follows
ar ar
ci(j + 1) ci(j )  a ijm i = aij ci(j ):
i i

14
 Since the algorithm has assigned xj = 1, we obtain:
Xm Xm ar
[ci(j + 1) ci(j )]  aij ci(j )  bj :
i=1 i=1 i
2

Theorem 2.12 The algorithm for on-line resource management benet problems with
integer variables is 2-competitive if the on-line algorithm has log  times more resources
than the optimal o-line algorithm.
Proof. Let ON = Pj2A bj be the benet achieved by the on-line algorithm. Let OPT be
the benet obtained by the optimal o-line algorithm. Lemma 2.8 together with Lemma
2.11 allow to state:
X X
kj X X
kj X
OPT = bj xj + bj xj r  1 + 2 bj = 1 + 2ON:
 r
j 2Q r=1 j 2A r=1 j 2A
2

2.4 Lower bounds for integer variables

Lower bounds for randomized algorithms for on-line resource management with integer
variables under restriction (1) follows from the lower bounds given by Awerbuch, Azar
and Plotkin [3] for the throughput version of the on-line virtual circuit routing problem
(see Section 5.3).
Theorem 2.13 Any deterministic or randomized algorithm for on-line resource manage-
ment benet problems with integer variables under restriction (1) has competitive ratio

(log (mBP )).

The above theorem shows that the proposed algorithm is optimal up to a constant
factor.

3 A methodology for on-line cost problems

In this section we study a class of cost problems, in which each job in the sequence must be
scheduled with one alternative chosen in a set of possible ones. Every alternative requires
a given amount for any of the resources available in the system. The goal is to balance
the load, i.e. to minimize the maximum scheduled amount of every single resource.
15
 Let faij g; i = 1; : : : ; m; be the resources associated with the alternative chosen by the
on-line algorithm to schedule job j and let faij g be the resources associated with the
alternative chosen by the o-line algorithm. Let ai(j ) = Pjk=1 aik and ai (j ) = Pjk=1 aik be
the amount of resource i scheduled by the on-line and by the optimal o-line algorithm
to schedule the rst j jobs. Let ON = maxfi21;:::;mgai (n) and OPT = maxfi21;:::;mg ai (n)
be the maximum amount of any single resource assigned at the end of the sequence by
the on-line and by the optimal o-line algorithm, respectively.
The on-line algorithm uses the doubling technique of [1], to determine a value  such
that OPT    2OPT. Such technique consists of assigning initially  to the minimum
non-zero value taken by a coecient ai1 and running an algorithm that is -competitive if
  OPT. Every time the algorithm fails to be -competitive, the value of  is doubled.
As shown in [1], the doubling technique increases the competitive ratio of the overall
algorithm by a factor of 4.
Moreover, let z~ = z for any argument z.
When job j is presented, the on-line algorithm chooses the alternative that minimizes
X
m
(a~i(j)+~aij a~i(j) );
i=1
where  is a suitable constant to be specied later.
Theorem 3.1 The algorithm for on-line resource management cost problems is O(log m)-
competitive.
Proof. Consider the following potential function
X
m
(j ) = a~i(j) (2 a~i (j ));
i=1
where  is a constant to be specied later.
Assume that the on-line algorithm and the o-line algorithm schedule the j -th job with
alternative specied by coecients faij g and faij g, respectively. The potential function
changes as follows:

(j + 1) (j ) =
X
m
a~i (j)+~aij (2 a~i (j ) a~ij )
X
m
a~i(j) (2 a~i (j )) =
i=1 i=1
X((a~i(j)+~aij a~i(j))(2 a~(j )) a~ a~i(j)+~aij ) 
m
i ij
i=1
X
m
(2( a
~ i (j a
)+~ ij a j  a
 ) a~ij  ) = 
~ i ( ) ~ i (j ) a
~ i (j ) X
m
(2(a~ij 1) a~ij ):
i=1 i=1

16
 
Since a~ij = aij  1, if there exists a value  such that for x 2 [0; 1] it holds 2(x 1) 
x, then the potential function never increases. This is true for  = 23 .
It follows that ON ~
 (n)  (0) = 2m, since a~i (j )  1. Then, we obtain:
 ON  2m;
which implies
ON = O( log m):
Since   2OPT follows that ON = O(log m)OPT. 2
A lower bound of
(log m) [9] for the on-line assignment problem, that can be mod-
eled within our framework, immediately extends to our case. Therefore, the algorithm
proposed in this section is optimal up to a constant factor.

4 Jobs with limited execution

In the previous section we have considered jobs entering the system and requiring resources
to be processed. In that case, once a job has obtained the assignment of a resource, it
keeps it forever.
A more realistic model should consider a scenario in which resources can be assigned
to jobs only for a limited amount of time, and that jobs leave the system once they
have been processed. For instance, in packet routing problems we observe that delivered
packets leave the system, and that a packet takes resources over a communication link
only for the time necessary to cross such link. For on-line load balancing, Azar et al. [7]
study the problem when jobs are in the system only for a limited time with an approach
similar to that presented in the following.
To model this scenario we associate with every job j an arrival time t(j ), the time at
which job j is communicated to the algorithm; we also associate a maximum delay d(j ),
job j has to leave the system before time t(j ) + d(j ). Both t(j ) and d(j ) are assumed to
be integer values. Moreover, let D be the ratio between the maximum and the minimum
delay. Without loss of generality we consider d(j ) 2 [1; D] for any job j .
Also resources are discretized: every resource can be assigned to distinct jobs in suc-
cessive units of time. An alternative associated with a job indicates the use of a set of
resources, specifying for each resource the required amount and a set of time units (not
necessarily contiguous). We complement the framework described in previous sections, to
consider jobs that arrive over time and have limited execution.
17
 Let m be the number of distinct resources. Every constraint represents the use of a
single resource for one unit of time. We run a copy of the algorithm for the linear program
with 2mD constraints for jobs entering the system between time 2kD and (2k + 1)D and
a second one, again with 2mD constraints, for jobs entering the system between time
(2k + 1)D and 2(k + 1)D, with k = 0; 1; 2; : : :. The 2mD constraints are introduced to
model the use of m resources for 2D units of time. Any job entering the system between
time t and time t + D, leaves the system within time t +2D. Therefore, the jobs that have
been scheduled by the algorithms in two successive intervals do not con ict. In fact all
the jobs that enter the system during the previous interval have already left the system
when the new interval starts. We state the two following theorems for benet and cost
problems:
Theorem 4.1 There is an algorithm for on-line resource management benet problems
with jobs arriving over time that is O(log )-competitive, with  = 2m0 PB and m0 = 2mD,
both for real variables and for integer variables under restriction (1).
Proof. In the benet version we assume that every resource i is available for a limited
amount ai during any unit of time. We split this amount by assigning a fraction a2i to the
rst copy of the algorithm and a fraction a2i to the second copy of the algorithm. In this
way the solution obtained by combining the two algorithms is feasible. Since any step
of the algorithm for both integer and real variables (see Sections 2.1 and 2.3) assigns at
most a logarithmic fraction of any resource, an on-line algorithm having only one half of
the resources has a competitive ratio that is only a constant factor away from the case in
which the on-line and the o-line algorithm have the same resources: it is easy to verify
that the upper bounds given in Lemmas 2.2 and 2.8 hold up to a constant factor of 2. 2

Theorem 4.2 There exists an algorithm for on-line resource management cost problems
with jobs arriving over time that is O(log mD)-competitive.
Proof. In the cost version, any of the two algorithms is O(log mD) competitive with
respect to the maximum load of the optimal o-line algorithm. The obtained algorithm
sums the load of the two algorithms and hence, it is far from the competitive ratio of each
copy of the algorithm for at most a factor of 2. 2

18
5 Applications
The proposed methodology for on-line cost and benet problems nds many applications.
The benet version models fractional and integer packing problems [27, 26], and knapsack,
multi-knapsack and multiple choice knapsack [25] both for integer and real variables.
The benet version with real variables also models nancial problems as the unidi-
rectional currency exchange problem, already studied in [12], stated as follows. A xed
amount of a rst currency is available at the beginning of a trading period. Every day a
new exchange rate is announced, and the algorithm has to decide how much to convert
to a second currency. The goal is to maximize the amount of the second currency at the
end of the trading period. This problem can be formulated with a linear programming
problem with only one resource, whose capacity is the amount of the rst currency avail-
able at the beginning of the trading period. Every new exchange rate corresponds to a
new job, with coecient equal to 1, and benet equal to the exchange rate. The value of
the variable associated with the job is the amount of the rst currency exchanged at the
current rate.
The following more complex nancial scenario can also be modeled. Assume that
a set of limited resources is available, and the goal is to invest them in a sequence of
economic activities as to maximize the total revenue. Each job of the sequence species
the kind and the amount of resources necessary for any unit of production of the new
economic activity, and its revenue per unit of product. The algorithm has to determine
how many resources to invest in this economic activity. The formulation as an on-line
resource management benet problem is straightforward.
In the remainder of this section we concentrate on routing and scheduling applications.

5.1 On-line shop scheduling

In shop scheduling problems [28] we are given m kinds of machines M1 ; : : : ; Mm, and a
sequence of n jobs. Job j of the sequence requires to perform a set of j operations
Oj1; : : : ; Ojj . Operation Ojk requires processing time tjk on a machine of kind Mjk .
The operations associated with a job must be non overlapping and may follow some
precedence rules. If the order is linear, i.e. the operations have to be performed according
to a given sequence, the problem is called job-shop scheduling. In ow-shop scheduling
the precedence rules between operations are described by a partial order.
Job j enters the system at time t(j ) and has to leave the system before time t(j )+ d(j ),

19
with d(j ) 2 [1; D]. Time is discrete. Clearly, the sum of processing times of all the
operations of a job is less than d(j ), Pk=1
j
tjk  d(j ). We also assume that once an
operation has started, it cannot be interrupted. An operation Ojk that has started on a
machine of kind Mjk at time t, will take such machine until time t + tjk .
We will consider both the benet and cost version of shop-scheduling problems. In
the benet version we assume that no more than ai jobs at the same time can be assigned
to a machine of kind Mi : at most ai machines of kind Mi are available or, equivalently, a
machine of kind Mi can process in parallel at most ai jobs. In the corresponding on-line
cost problem the goal is that of minimizing the maximum number of machines of the same
kind or the maximum power of every single machine necessary to schedule all the jobs in
the sequence.
The formulation of shop scheduling as a resource management problem with jobs
arriving over time is then as follows:
 For every kind of machine Mi , i = 1; : : : ; m, there are 2D constraints; constraint cil ,
l = 1; : : : ; 2D, represents the use of machines of kind Mi for one unit of time.
 The set of alternatives of job j corresponds to the set of feasible schedules for the
set of operations associated with job j . Every feasible schedule is dened by a linear
order for the operations that is consistent with the precedence rules, and from the
time at which operation Ojk is scheduled on a machine of kind Mjk . Namely, we
have arcilj = 1 if job j is scheduled on a machine of kind Mi for the unit of time
represented by constraint cil , arcilj = 0 otherwise.
Observe that there could be an exponential number of alternatives for any job. We
show a procedure polynomial in m and D to select an alternative of minimum cost for
on-line job-shop scheduling.
Theorem 5.1 There exists an O(log )-competitive algorithm,  = mDPB , for the ben-
et version under restriction (1), and an O(log mD)-competitive algorithm for the cost
version of on-line shop scheduling. For on-line job-shop scheduling, the running time of
the algorithms that process a job is polynomial in m and D.
Proof.
The rst part of the theorem derives from the previous discussion and from theorems
4.1 and 4.2.
For the second part of the claim, we describe a procedure for selecting an alternative of
minimum cost (see Section 2.3 and 3) for any job in job-shop scheduling that runs in time
20
polynomial in m and D . Assume that the linear order of the operations is identied by
the sequence Oj1; : : : ; Ojj for a generic job j . The problem is solved through a reduction
to the shortest path problem in a layered graph.
N = f(k; t)jk = 1; : : : ; j + 1; t = 0; : : : ; d(j )g is the set of vertices of the graph. Every
vertex of the graph is denoted by an index of column and an index of row. There are
(d(j ) + 1)(j + 1) vertices in the graph.
All edges of the graph are directed from vertices with smaller index of column to
vertices with higher index of column. The set of edges is given by the union of two
disjoint sets E1 and E2 . Edges in E1 model the situation in which a job is waiting for
the assignment to a machine. These edges connect any pair of successive vertices on
any row, and are weighted 0 since no resource is assigned to the job. Namely, E1 =
f((k; t); (k; t + 1))jk = 1; : : : ; j + 1; t = 0; : : : ; d(j ) 1g.
The second set of edges E2 models the assignment of job j to a machine of kind Mjk
at some time t for tjk units of time. For any operation k = 1; : : : ; j and for any time
t = 0; : : : ; d(j ) 1, an edge connects vertex (k; t) to vertex (k + 1; t + tjk ) if t + tjk  d(j ),
and has weight equal to the sum of the exponential costs of the resources assigned to the
job, namely a machine of kind Mjk from time t to time t + tjk .
The choice of an alternative of minimum cost corresponds to a shortest path connecting
vertex (1; 0) to vertex (j + 1; d(j )). A scheduling for the job is obtained from the edges
of the shortest path. Notice that any path from the rst row to the last row has to cross
j edges that denote a schedule for the sequence of operations. Therefore, the running
time of the procedure is polynomial in m and d(j ).
There also exists a competitive algorithm for ow-shop scheduling. However, there is
in general an exponential number of feasible sequences of operations, and then the running
time of the algorithm is not polynomial. 2
Assume that the time required for a single operation is at most T . Analogously to
the lower bounds of Section 2.2, a lower bound of
(log T ) can be proved for the benet
version of job-shop scheduling, with real variables and integer variables under restriction
1. Thus, the proposed algorithms for the benet version are optimal up to a constant
factor if D is of the order of mTBP . Similarly, for the cost version, if D is of the order
of m then the algorithm is optimal up to a constant factor.

21
5.2 On-line packet routing
A special interesting case of on-line resource management with jobs arriving over time is
packet routing. Job j , presented at time t(j ), requires to deliver a packet from a source
node s(j ) to a destination node r(j ) within a maximum delay d(j ). One unit of time is
required to cross any edge of the network.
Packet routing can be formulated with our methodology by modeling the use of a link
in the network for one unit of time with a distinct resource. Every feasible alternative
to deliver the packet consists of the edges forming a path from the source node to the
destination node, and the time schedule at which every edge in the path is crossed.
The on-line cost version of packet routing consists of minimizing the maximum band-
width on any link that is necessary to deliver all the packets within a maximum delay.
The benet version consists of maximizing the benet over a sequence of packets delivered
within a maximum delay.
Theorem 5.2 There exists an O(log mDBP )-competitive algorithm for the benet ver-
sion under restriction (1), and an O(log mD)-competitive algorithm for the cost version
of on-line packet routing. The running time of the algorithms that process each packet is
polynomial in m and D.
Proof.
Similarly to the case of on-line job-shop scheduling, the problem of choosing an alter-
native with minimum cost is reduced to a shortest path problem in a layered graph.
We model the network with a graph G = (N; E ), jN j = n. The corresponding layered
graph G = (N; E ) has set of vertices N = f(u; t)ju 2 N; t = 0; : : : ; d(j )g, i.e. every
vertex has an index of row given by the corresponding vertex of the communication
network, and an index of column given by the (discrete) time at which the packet crosses
a communication link leaving that vertex of the network.
There are edges only between adjacent layers, i.e. they are directed from layer t to
layer t + 1. Every edge in a rst set E 1 = f((u; t); (u; t + 1))ju 2 N; t = 0; : : : ; D 1g
is weighted with 0 and models the situation in which a packet is waiting at vertex u
to be transmitted to an adjacent vertex in the network. A second set of edges E 2 =
f((u; t); (v; t +1))j(u; v) 2 E g models the transmission of a packet from vertex u to vertex
v at some time t. Namely, vertex (u; t) in layer t is connected to any vertex (v; t + 1) in
layer t + 1 such that (u; v) 2 E .
Assume that at time t(j ) a request to send a packet from source node s(j ) to destina-
tion node r(j ) is issued. Any edge ((u; t); (v; t +1)) in E 2 is weighted with the exponential
22
cost associated to the constraint that model the use of edge (u; v) in the transmission net-
work between time t(j ) + t and time t(j ) + t + 1. The problem of selecting an alternative
with minimum cost is thus reduced to the search of a shortest path in the directed lay-
ered graph from vertex (s(j ); 0) to vertex (r(j ); d(j )) where d(j ) is the maximum delay
accepted for the packet. The set of communication links crossed by the packet and the
schedule at which such edges are crossed is determined by the edges in the shortest path
that connect dierent rows in the layered graph.
2
If we assume that the maximum deadline is of the order of mPB , then, Theorems 2.5,
2.6 and 2.7, imply that the proposed algorithm for on-line packet routing is optimal up
to a constant factor.

5.3 Virtual circuit routing and multiprocessor scheduling

We have already mentioned that on-line virtual circuit routing and on-line multiprocessor
scheduling can be modeled within our framework. We then obtain, as a result of our
approach, the results of [1, 3].
For virtual circuit routing, the j -th call entering the system asks for the establishment
of a communication between two nodes in the network at a certain transmission rate r(j )
for a duration d(j ). Each link has bandwidth ai . If the communication request of the
j -th call is scheduled with a certain path connecting the two nodes, then the occupied
bandwidth is increased by r(j ) over each link in the path, and a benet bj is gained by
the algorithm. Assume that the benet bj ranges in the interval [1; B ], the ratio arji in the
range [1=P; 1] and the duration d(j ) is an integer value in the range [1; D].
This problem can be modeled as on-line resource management problem, and hence, by
Theorem 2.10, we obtain a (1 + log )-competitive algorithm for the benet version with
integer variables, under restriction 1, with  = 2mDBP , an improvement by a constant
factor of 2 of the result given in [3].
With regard to parallel machine scheduling, every job has to be assigned to one among
the set of machines. If machines are unrelated, every job may require a dierent load
on any single machine. The goal is that of minimizing the maximum load over all the
machines to deal with a sequence of jobs. In the load version of virtual circuit routing,
the goal is that of minimizing the maximum bandwidth on any communication link in
the network as to accommodate all requests in the sequence. It is now straightforward

23
to model these two problems as on-line resource management problems, thus yielding
optimal competitive algorithms with logarithmic competitive ratio as in [1].

6 Conclusions and open problems

In this paper we have presented a framework for on-line resource management problems
and we have proposed logarithmic upper bounds optimal up to a constant factor. We
have also shown that many on-line problems can be studied in this framework.
Finally we mention open problems. The most interesting problem is to nd competitive
algorithms in the case of integer values when restriction (1) is released. A recent result
p
[11] establishes an
( m) lower bound on the competitive ratio of randomized algorithms
for the on-line edge-disjoint path problem when a pair of vertices can be connected using a
single xed path, where m is the number of edges of the network. (This bound is also tight
p
[14].) It implies an
( m) lower bound for the case of integer values, since our framework
models this problem with m being the number of resources available. However, it would
be interesting to nd under which conditions polylogarithmic competitive randomized
algorithms are possible. Observe that for a particular case that models on-line virtual
circuit routing, such positive results are known for dierent network topologies (see Section
1).
In Section 5.1, on-line algorithms with logarithmic competitive ratio have been de-
vised for shop scheduling problems and packet routing. We recall that the algorithm for
ow-shop scheduling is not polynomial, since the set of sequences of operations that are
consistent with a given partial order has exponential size. An interesting question is to
devise a polynomial algorithm with polylogarithmic competitive ratio for this problem.
For on-line packet routing, and virtual circuit routing, it would be relevant to devise an
ecient distributed implementation of the algorithm.
Acknowledgments. A special thank is due to Yossi Azar and Amos Fiat. We would
also like to thank Yair Bartal, Anna Karlin and Adi Rosen for useful discussions and an
anonymous referee for improving the presentation of the paper.

References
[1] J. Aspnes, Y. Azar, A. Fiat, S. Plotkin and O. Waarts, \On-line load balancing
with applications to machine scheduling and virtual circuit routing", Proceedings of

24
 the 23rd Annual ACM Symposium on Theory of Computing, pp. 623-631, 1993.
[2] B. Awerbuch, Y. Azar and A. Fiat, \Packet Routing via min-cost circuit routing",
Proceedings of 4th Israeli Symposium on Theory of Computing and Systems, pp.
37-42, 1996.
[3] B. Awerbuch, Y. Azar and S. Plotkin, \Throughput competitive on-line routing",
Proceedings of the 34th Annual Symposium on Foundations of Computer Science,
pp. 32-40, 1993.
[4] B. Awerbuch, Y. Azar, S. Plotkin and O. Waarts, \Competitive routing of vir-
tual circuits with unknown duration", Proceedings of the 5th Annual ACM-SIAM
Symposium on Discrete Algorithms, pp. 321-327, 1994.
[5] B. Awerbuch, Y. Bartal, A. Fiat and A. Rosen, \ Competitive non-preemptive call
control", Proceedings of the 5th ACM-SIAM Symposium on Discrete Algorithms,
pp. 312-320, 1994.
[6] Y. Azar, A.Z. Broder and A.R. Karlin, \On-line load-balancing", Proceedings of the
33rd Annual Symposium on Foundations of Computer Science, pp. 218-225, 1992.
[7] Y. Azar, B. Kalyanasundaram, S. Plotkin, K.R. Pruhs and O. Waarts, \On-line
load balancing of temporary tasks", Proceedings of the 2nd International Workshop
on Algorithms and data Structures, pp. 119-130, 1993.
[8] B. Awerbuch, R. Gawlick, F.T. Leighton and Y. Rabani, \On-line admission con-
trol and circuit routing for high performance computing and communication", Pro-
ceedings of the 35th Annual Symposium on Foundations of Computer Science, pp.
412-423, 1994.
[9] Y. Azar, J. Naor and R. Rom, \The competitiveness of on-line assignment", Pro-
ceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms, pp. 203-210,
1992.
[10] S. Ben-David, A. Borodin, R.M. Karp, G. Tardos and A. Widgerson, \On the
power of randomization in on-line algorithms", Proceedings of the 22nd Annual
ACM Symposium on Theory of Computing, pp. 379-386, 1990.

25
[11] Y. Bartal, A. Fiat and S. Leonardi, \Lower bounds for on-line graph problems with
application to on-line circuit and optical routing", Proceedings of the 28-th Annual
ACM Symposium on Theory of Computing (STOC 96), pp. 531-540, 1996.
[12] R. El-Yaniv, A. Fiat, R.M. Karp and G. Turpin, \Competitive analysis of nancial
games", Proceedings of the 33rd Annual Symposium on Foundations of Computer
Science, pp. 327-333, 1992.
[13] R. El-Yaniv and R.M. Karp, \The mortgage problem", Proceedings of the 2nd Israel
Symposium on Theory of Computing and Systems, 1993.
[14] A. Fiat, personal communication, 1994.
[15] A. Fiat, R.M. Karp, M. Luby, L.A. McGeoch, D.D. Sleator and N.E. Young, \Com-
petitive paging algorithms", Journal of Algorithms 12, pp. 685-699, 1991.
[16] A. Fiat, Y. Rabani and Y. Ravid, \Competitive k-server algorithms", Proceedings
of the 31st Annual Symposium on Foundations of Computer Science, pp. 454-463,
1990.
[17] R.L. Graham, \Bounds for certain multiprocessing anomalies", Bell Syst. Tech. J.
45:1563-1581, 1966.
[18] J. Garay, I. Gopal, S. Kutten, Y. Mansour and M. Yung, \Ecient on-line call-
control algorithms", Proceedings of the 2nd Annual Israel Conference on Theory of
Computing and Systems, pp. 285-293, 1993.
[19] A.R. Karlin, M.S. Manasse, L. Rudolph and D.D. Sleator, \Competitive snoopy
caching", Algorithmica, 3(1):70-119, 1988.
[20] R.M. Karp, \On-line algorithms versus o-line algorithms: how much is it worth to
know the future?", Proceedings of the World Computer Congress, 1992.
[21] J. Kleinberg and E. Tardos, \Disjoint paths in densely embedded graphs", Pro-
ceedings of the 36th Annual Symposium on Foundations of Computer Science, pp.
52-61, 1995.
[22] J.K. Lenstra and A.H.G. Rinnooy Kan, \An introduction to multiprocessor schedul-
ing", Technical Report, CWI, Amsterdam, 1988.

26
[23] R.J. Lipton and A. Tomkins, \On-line interval scheduling", Proceedings of the 5th
ACM-SIAM Symposium on Discrete Algorithms, pp. 302-311, 1994.
[24] M.S. Manasse, L.A. McGeoch and D. Sleator, \Competitive algorithms for on-line
problems", Proceedings of the 20th ACM Symposium on Theory of Computing, pp.
322-333, 1988.
[25] S. Martello and P. Toth, Knapsack problem, Wiley, 1990.
[26] S. Plotkin, D. Shmoys and E. Tardos, \Fast approximation algorithms for fractional
packing and covering problems", Proceedings of the 32nd IEEE Annual Symposium
on Foundations of Computer Science, pp. 495-504, 1991.
[27] P. Raghavan, \Probabilistic construction of deterministic algorithms: approximat-
ing packing integer programs", Journal of Computer and System Science 37, pp.
130-143, 1988.
[28] D.B. Shmoys, C. Stein, J. Wein, \Improved approximation algorithms for shop
scheduling problems", Proceedings of the 2nd ACM-SIAM Symposium on Discrete
Algorithms, pp. 148-157, 1991.
[29] D.B. Shmoys, J. Wein, D.P. Williamson, \Scheduling parallel machines on-line",
Proceedings of the 32nd Annual Symposium on Foundations of Computer Science,
pp. 131-140, 1991.
[30] D. Sleator and R.E. Tarjan, \Amortized eciency of list update and paging rules",
Communications of ACM 28, pp. 202-208 (1985).
[31] A.S. Tannenbaum, Computer networks, Prentice Hall, 1989.

27