Beyond Competitive Analysis.
The competitive analysis of online algorithms has been criticized as being too crude and unrealistic. We propose refinements of competitive analysis in two directions: The first restricts the power of the adversary by allowing only certain input distributions, while the other allows for comparisons between information regimes for online decision-making.  We illustrate the first with an application to the paging problem; as a byproduct we characterize completely the work functions of this important special case of the k-server problem.  We use the second refinement to explore the power of lookahead in server and task systems.
Introduction
The area of On-Line Algorithms [16, 10] shares with Complexity Theory the
following characteristic: Although its importance cannot be reasonably denied
(an algorithmic theory of decision-making under uncertainty is of obvious
practical relevance and significance), certain aspects of its basic premises,
modeling assumptions, and results have been widely criticized with respect
to their realism and relation to computational practice. We think that now
is a good time to revisit some of the most often-voiced criticisms of competitive
analysis (the basic framework within which on-line algorithms have
Computer Science Department, University of California, Los Angeles, CA 90095. Re-search
supported in part by NSF grant CCR-9521606.
y Computer Science and Engineering, University of California, San Diego, La Jolla, CA
92093. Research supported in part by the National Science Foundation.
been heretofore studied and analyzed), and to propose and explore some
better-motivated alternatives.
In competitive analysis, the performance of an on-line algorithm is compared
against an all-powerful adversary on a worst-case input. The competitive
ratio of a problem-the analog of worst-case asymptotic complexity for
this area-is defined as
(1)
Here A ranges over all on-line algorithms, x over all "inputs", opt denotes
the optimum off-line algorithm, while A(x) is the cost of algorithm A when
presented with input x. This clever definition is both the weakness and
strength of competitive analysis. It is a strength because the setting is clear,
the problems are crisp and sometimes deep, and the results often elegant
and striking. But it is a weakness for several reasons. First, in the face of
the devastating comparison against an all-powerful off-line algorithm, a wide
range of on-line algorithms (good, bad, and mediocre) fare equally badly;
the competitive ratio is thus not very informative, fails to discriminate and
to suggest good approaches. Another aspect of the same problem is that,
since a worst-case input decides the performance of the algorithm, the optimal
algorithms are often unnatural and impractical, and the bounds too
pessimistic to be informative in practice. Even enhancing the capabilities of
the on-line algorithm in obviously desirable ways (such as a limited lookahead
capability) brings no improvement to the ratio (this is discussed more extensively
in a few paragraphs). The main argument for competitive analysis
over the classical expectation maximization is that the distribution is usually
not known. However, competitive analysis takes this argument way too far:
It assumes that absolutely nothing is known about the distribution, that any
distribution of the inputs is in principle possible; the worst-case "distribu-
tion" prevailing in competitive analysis is, of course, a worst-case input with
probability one. Such complete powerlessness seems unrealistic to both the
practitioner (we always know, or can learn, something about the distribution
of the inputs) and the theoretician of another persuasion (the absence of a
prior distribution, or some information about it, seems very unrealistic to a
probabilist or mathematical economist).
The paging problem, perhaps the most simple, fundamental, and practically
important on-line problem, is a good illustration of all these points.
An unreasonably wide range of deterministic algorithms (both the good in
practice LRU and the empirically mediocre FIFO) have the same competitive
ratio-k, the amount of available memory. Even algorithms within more
powerful information regimes-for example, any algorithm with lookahead
pages-provably can fare no better. Admittedly, there have been
several interesting variants of the framework that were at least partially successful
in addressing some of these concerns. Randomized paging algorithms
have more realistic performance [5, 11, 15]. Some alternative approaches to
evaluating on-line algorithms were proposed in [1, 14] for the general case
and in [2, 6, 7, 17] specifically for the paging problem.
In this paper we propose and study two refinements of competitive analysis
which seem to go a long way towards addressing the concerns expressed above.
Perhaps more importantly, we show that these ideas give rise to interesting
algorithmic and analytical problems (which we have only begun to solve in
this paper).
Our first refinement, the diffuse adversary model, removes the assumption
that we know nothing about the distribution-without resorting to the
equally unrealistic classical assumption that we know all about it. We assume
that the actual distribution D of the inputs is a member of a known
class \Delta of possible distributions. That is, we seek to determine, for a given
class of distributions \Delta, the performance ratio
A
ED (A(x))
ED (opt(x))
(2)
That is, the adversary picks a distribution D among those in \Delta, so that the
expected, under D, performance of the algorithm and the off-line optimum
algorithm are as far apart as possible. Notice that, if \Delta is the class of all
possible distributions, (1) and (2) coincide since the worst possible distribution
is the one that assigns probability one to the worst-case input and
probability zero everywhere else. Hence the diffuse adversary model is indeed
a refinement of competitive analysis.
In the paging problem, for example, the input distribution specifies, for
each page a and sequence of page requests ae, prob(ajae)-the probability that
the next page fault is a, given that the sequence so far is ae. It is unlikely that
an operating system knows this distribution precisely. On the other hand,
it seems unrealistic to assume that any distribution at all is possible. For
example, suppose that the next page request is not predictable with absolute
certainty: prob(ajae) - ffl, for all a and ae, where ffl is a real number between
capturing the inherent uncertainty of the request sequence. This
is a simple, natural, and quite well-motivated assumption; call the class of
distributions obeying this inequality \Delta ffl . An immediate question is, what is
the resulting competitive ratio
As it turns out, the answer is quite interesting. If k is the storage capacity,
the ratio shown to coincide with the expected cost of a simple
random walk on a directed graph with approximately
nodes. For
this value is easy to estimate: It is between 1
ffl; for
larger values of k we do not have a closed-form solution for the ratio. There
are two important byproducts of this analysis: First, extending the work in
[8], we completely characterize the work functions of the paging special case
of the k-server problem. Second, the optimum on-line algorithm is robust-
that is, the same for all ffl's-and turns out to be a familiar algorithm that
is also very good in practice: LRU. It is very interesting that LRU emerges
from the analysis as the unique "natural" optimal algorithm, although there
are other algorithms that are also optimal.
The second refinement of competitive analysis that we are proposing deals
with the following line of criticism: In traditional competitive analysis, the
all-powerful adversary frustrates not only interesting algorithms, but also
powerful information regimes. The classical example is again from paging:
In paging the best competitive ratio of any on-line algorithm is k. But
what if we have an on-line algorithm with a lookahead of ' steps, that is,
an algorithm that knows the immediate future? It is easy to see that any
such algorithm must fare equally badly as algorithms without lookahead. In
proof, consider a worst case request sequence abdc \Delta \Delta \Delta and take its ('
stuttered version, a '+1 b '+1 d '+1 c '+1 \Delta \Delta \Delta It is easy to see that an algorithm with
lookahead ' is as powerless in the face of such a sequence as one without a
lookahead. Once more, the absolute power of the adversary blurs practically
important distinctions. Still, lookahead is obviously a valuable feature of
paging algorithms. How can we use competitive analysis to evaluate its
power? Notice that this is not a question about the effectiveness of a single
algorithm, but about classes of algorithms, about the power of information
regimes-ultimately, about the value of information [12].
To formulate and answer this and similar questions we introduce our
second refinement of competitive analysis, which we call comparative analysis.
Suppose that A and B are classes of algorithms-typically but not necessarily
usually a broader class of algorithms, a more powerful
information regime. The comparative ratio R(A;B) is defined as follows:
min A2A
This definition is best understood in terms of a game-theoretic interpre-
tation: B wants to demonstrate to A that it is a much more powerful class
of algorithms. To this end, B proposes an algorithm B among its own. In
response, A comes up with an algorithm A. Then B chooses an input x.
Finally, A pays B the ratio A(x)=B(x). The larger this ratio, the more powerful
B is in comparison to A. Notice that, if we let A be the class of on-line
algorithms and B the class of all algorithms-on-line or off-line-then equations
(1) and (3) coincide, and Hence comparative analysis is
indeed a refinement of competitive analysis.
We illustrate the use of comparative analysis by attacking the question
of the power of lookahead in on-line problems of the "server" type: If L ' is
the class of all algorithms with lookahead ', and L 0 is the class of on-line
algorithms, then we know that, in the very general context of metrical task
systems [3] we have
(that is, the ratio is at most 2' systems, and it is
exactly while in the more restricted context of paging
Diffuse Adversaries
The competitive ratio for a diffuse adversary 1 is given in equation (2). In
order to factor out the disadvantage of the algorithm imposed by the initial
conditions, we shall allow an additive constant in the numerator. More
precisely, an on-line algorithm A is c-competitive against a class \Delta of input
distributions if there exists a constant d such that for all distributions D 2 \Delta:
Diffuse adversaries are not related to the diffusion processes in probability theory
which are continuous path Markov processes.
The competitive ratio of the algorithm A is the infimum of all such c's. Fi-
nally, the competitive ratio R(\Delta) of the class of distributions is the minimum
competitive ratio achievable by an on-line algorithm. It is important to observe
that \Delta is a class of acceptable conditional probability distributions; each
is the distribution of the relevant part of the world conditioned on the
currently available information. In the case of the paging problem with a set
of pages M , \Delta may be any set of functions of the form
where for all ae 2 M   P
1. In the game-theoretic interpretation,
as the sequence of requests ae develops, the adversary chooses the values of
D(ajae) from those available in \Delta to maximize the ratio. Since we deal with
deterministic algorithms, the adversary knows precisely the past decisions
of A, but the adversary's choices may be severely constrained by \Delta. It is
indicative of the power of the diffuse adversary model that most of the proposals
for a more realistic competitive analysis are simply special cases of it.
For example, the locality of reference in the paging problem [2, 6] is captured
by the diffuse adversary model where \Delta consists of the following conditional
probability distributions: there is no edge from b to a in the
access graph and otherwise. Simirarly, the Markov paging
model [7] and the statistical adversary model [14] are also special cases of
the diffuse adversary model.
In this section we apply the diffuse adversary model to the paging prob-
lem. We shall focus on the class of distributions \Delta ffl , which contains all
functions ffl]-that is to say, all conditional distributions
with no value exceeding ffl. Since the paging problem is the k-server problem
on uniform metric spaces, we shall need certain key concepts from the
k-server theory (see [8, 4] for a more detailed exposition).
denote the number of page slots in fast memory, and let
M be the set of pages. A configuration is a k-subset of M ; we denote the
set of all configurations by C. Let ae 2 M   . The work function associated
with ae, w ae (or w when ae is not important or understood from context) is a
function defined as follows: If (X) is the
optimum number of page faults when the sequence of requests is ae and the
final memory configuration is X.
Henceforth we use the symbols to denote set union and set
difference respectively. Also, we represent unary sets with their element, e.g.
we write a instead of fag.
Definition 2 If w is a work function, define the support of w to be all
configurations such that there is no Y 2 C, different from X, with
j. Intuitively, the values of w on its support completely
determine w.
The following lemmata, specific for the paging problem and not true in
general for the k-server problem, characterize all possible work functions by
determining the structure of their support. A similar, but more complicated,
characterization is implicit in the work of [11]. The first lemma states that
all values in the support are the same, and hence what matters is the support
itself, not the values of w on it.
Lemma 1 The support of a work function w contains only configurations
on which w achieves its minimum value.
Proof. The proof is by contradiction. Suppose that the lemma does not
hold. That is, there is a configuration A in the support of w such that
Choose now a configuration B with w(B) ! w(A)
that minimizes jB \Gamma Aj. By the quasiconvexity condition in [8], there is an
a A such that
This can hold only if either w(A) ?
In the first case, we get that 1 and this contradicts
the assumption that A is in the support of w. The second case also leads
to a contradiction since it violates the choice of B with minimum
because
An immediate consequence of Lemma 1 is that the off-line cost is always
equal to the minimum value of a work function. The next lemma determines
the structure of the support.
Lemma 2 For each work function w there is an increasing sequence of sets
the most recent request, such that the
support of w is precisely
Note that the converse, not needed in the sequel, also holds: Any such tower
of P j 's defines a reachable work function. For a work function w define its
signature to be the k-tuple its type to be the k-tuple
Proof. The proof is by induction on the length of the request sequence. The
basis case is obvious: Let P is the initial
configuration. For the induction step assume that we have the signature
be the resulting work function after request
r.
Consider first the case that r belongs to P t and not to P
kg. Since there is at least one configuration in the support of
w that contains the request r, the minimum value of w 0 is the same with the
minimum value of w. Therefore, the support of w 0 is a subset of the support
of w. It consists of the configurations that belong to the support of w and
contain the last request r. It is easy now to verify that the signature of w 0
is:
If, on the other hand, the request r does not belong to P k , the minimum value
of w 0 is one more than the minimum value of w. In this case, the support
of w 0 consists of all configurations in the support of w where one point has
been replaced by the request r, i.e. a server has been moved to service r.
Consequently, the signature of w 0 is given by:
The induction step now follows.
We now turn to the \Delta ffl diffuse adversary. Let w be the current work
function with signature
We want to determine the optimal on-line and off-line strategies. A natural
guess is that the best on-line strategy should prefer to have in the fast memory
pages from P i than pages from P j. The reason is that pages
in P i are more valuable to the off-line algorithm than pages in P
a configuration from the support of w remains in the support when we replace
any page from P a page from P i ; the converse does not hold in
general.
For the same reason the off-line strategy should prefer the next request to
be in P i than in Furthermore, the adversary should try to avoid placing
a request in a page already in the on-line fast memory, because although
this doesn't affect the on-line cost, it may shrink the support of the current
work function. This leads to the following strategy for the adversary: First,
order all pages in such a way that pages in P i precede pages in P
pages in P k precede pages in P k , the complement of
Call such an ordering a canonical ordering with respect to the signature
. The adversary now assigns probability ffl to the first 1=ffl pages of a
canonical ordering that are not in the on-line fast memory. Notice that this
presupposes that there are at least k + 1=ffl pages in total. Although, both
strategies seem optimal, we don't have a simple proof for this. Instead, we
will proceed carefully to establish that this is in fact the case.
But first we analyze the competitive ratio that results from the above
strategies. It is not difficult to see that the off-line cost is the expected cost
of a Markov chain M k;ffl : The states of M k;ffl are the types of the work functions,
i.e., all tuples (p From
a state (p 1 which corresponds to a signature
there are transitions to the following (not necessarily distinct)
They correspond to the case of the next request r being in P t ,
the case of corresponds to simply repeating the last request and we can
safely omit it. There is also a transition to the type
that corresponds to the case r 62 P k . The cost of each transition is the
associated off-line cost. All transitions have cost zero, except the last one,
which has cost one, because a request r increases the minimum value of the
work function if and only if r 62 P k .
Finally, the transition probabilities are determined by the adversary's
strategy. The total probability of the first t transitions is maxf(p
(each page that is not in on-line fast memory has probability ffl). The probability
of the last transition is the remaining probability
also shows that there is no need to consider types with p k greater than k+1=ffl
because these types are 'unreachable'. The significance of this fact is that
the Markov process M k;ffl is finite (it has O((k
Let c(M k;ffl ) be the expected cost of each step of the Markov process M k;ffl ,
which is also the expected off-line cost. If we assume that the on-line cost of
each step is one, we get that the competitive ratio resulting from the above
strategies is 1=M k;ffl .
We now turn our attention to the optimal strategy for the adversary. It
should be clear that in each step the adversary assigns probabilities to pages
which are not in the on-line fast memory, based on the current work function
and the configuration of the on-line algorithm. Our aim is to make the
adversary's strategy independent of the configuration of the on-line algorithm
and this can be achieved by allowing the on-line algorithm to swap any two
pages without any extra cost immediately after servicing a request. The on-line
algorithm suffers one page fault in each step, but it can move to the best
configuration relative to the current work function with no extra penalty.
Consider now a work function w with signature
We will first argue that the optimal strategy for
the adversary prefers to assign probability to pages in P i than to pages in
j. The reason is that the type (1;
of the resulting work function w 1 after a request in P i is
no less than the type
of the resulting work function w 2 after a request in P precisely,
by symmetry and the assumption that the on-line algorithm is always at the
best configuration, the only relevant part of a work function to the off-line
strategy is its type. Therefore, instead of comparing w 2 directly to w 1 we
can compare w 2 to any work function w 0
1 that has the same type as w 1 . It is
easy to see that there is a work function w 0
1 with the same type as w 1 such
that any configuration in the support of w 2 belongs to the support of w 0
1 .
Consequently, for any request sequence ae the off-line cost to service it with
initial function w 0
1 is no more than the off-line cost to service ae with initial
work function w 2 .
Similarly, we will argue that the optimal adversary prefers to assign probability
to pages in P k than to pages in P k . However, there is a trade-off
involved when the adversary assigns probability to pages in P k : The adversary
suffers an immediate page fault but the support of the resulting work
function is larger and therefore the adversary will pay less in the future. We
want to verify that the adversary never recovers a future payoff larger than
the current loss (the page fault). Again, we cannot directly compare the two
work functions w 1 and w 2 that result from a request in P k and a request in P k
respectively, but it suffices to compare w 1 with a work function w 0
2 that has
the same type with w 2 . The next lemma shows that for any request sequence
ae the cost of servicing it with initial work function w 1 differs by at most one
from the cost of servicing it with initial work function w 0
. As we argued
above, the worst case happens when the request in P k is actually a request in
therefore we need to compare two work functions with types
1).
In the next lemma we use for simplicity q
Lemma 3 Let w 1 be a work function with type (1;
Then there is a work function w 2 with type (1; 2; such that for
any configuration in the support of w 1 there is a configuration in the support
of w 2 that differs in at most one position.
Proof. Let be the signature of w 1 and let a be a page in
be the work function with signature
Consider a configuration X in the support of w 1 . We will show that there
exists a configuration Y in the support of w 2 such that jY \Gamma Xj - 1. Consider
a canonical ordering with respect to the signature of w 2 and let x k be the
last page of X in this order. Also, let b be the first page in this ordering
not in X \Gamma x k . We claim that differs in at most one
position from X, is in the support of w 2 . Notice first that Y contains the
page in P 1 . It also contains the page a, since a is in the the second place in
the ordering and therefore either a 2 X or a = b. It remains to show that
1. There are two cases to consider: The
first case, when 1, follows from the fact that x k is in P j only
if b is in P j . For the second case, when suffices to note that
In summary, assuming that the on-line algorithm suffers cost one in each
step but can swap pages freely, the optimum strategy for the adversary is to
assign probabilities to pages which are not in the fast on-line memory and
are first in a canonical ordering with respect to the current signature. On
the other hand, the on-line strategy should prefer to have in its fast memory
the first pages of this ordering. Therefore, if a 1 ; a is a canonical ordering
then the best configuration for an on-line algorithm is g. This
poses the question whether it is always possible for the on-line algorithm to
be in such a configuration by a simple swap in each step. Fortunately, there
is a familiar algorithm that does exactly this: the Least Recently Used (LRU)
algorithm. Surprisingly, LRU does not even remember the whole signature
of the work function. It simply remembers the first k pages a 1 ; a of a
canonical ordering, and services the next request by swapping the a k page. It
is easy to verify that after the next request, its fast memory contains the first
k pages of some canonical ordering with respect to the resulting signature.
Therefore, we have shown:
Theorem 1 When there are at least k+1=ffl pages, algorithm LRU is optimal
against a diffuse adversary with competitive ratio 1=c(M k;ffl ).
It seems difficult to determine the exact competitive ratio 1=c(M k;ffl ). For
the extreme values of ffl we know that 1. The
first case is when the adversary has complete power and the second when
the adversary suffers a page fault in almost every step. In fact, the next
corollary suggests that the competitive ratio may not be expressible by a
simple closed-form expression. It remains an open problem to find a simple
approximation for the competitive ratio.
Corollary 1 If and 1=ffl is an integer then
Y
Therefore,
ffl.
Proof. It is not difficult to see that the Markov process is identical to
the following random process: in each phase repeatedly choose uniformly
a number from f1; phase ends when a number
is chosen twice. This random process is a generalization of the well-known
birthday problem in probability theory. A phase corresponds to a cycle in the
Markov chain that starts (and ends) at state with type (1; 2). The cost of
the Markov chain is the expected length of a phase minus one (all transitions
in the cycle have cost one except the last one). It is not hard now to verify
the expression for R(ffl).
In order to bound the expected length of a phase, notice that each of the
first
n numbers has probability at most 1=
p n to end the phase. In contrast,
each of the next
n numbers has probability at least 1=
n to end the phase.
Elaborating on this observation we get that 1
ffl.
Comparative Analysis
On-line algorithms deal with the relations between information regimes. Formally
but briefly, an information regime is the class of all functions from a
domain D to a range R which are constant within a fixed partition of D.
Refining this partition results in a richer regime. Traditionally, the literature
on on-line algorithms has been preoccupied with comparisons between two
basic information regimes: The on-line and the off-line regime (the off-line
regime corresponds to the fully refined partition). As we argued in the intro-
duction, this has left unexplored several intricate comparisons between other
important information regimes.
Comparative analysis is a generalization of competitive analysis allowing
comparisons between arbitrary information regimes, via the comparative ratio
defined in equation (3). Naturally, such comparisons make sense only if
the corresponding regimes are rich in algorithms-single algorithms do not
lend themselves to useful comparisons. As in the case of the competitive
ratio for the diffuse adversary model, we usually allow an additive constant
in the numerator of equation (3).
We apply comparative analysis in order to evaluate the power of lookahead
in task systems. An on-line algorithm for a metrical task system has lookahead
if it can base its decision not only on the past, but also on the next '
requests. All on-line algorithms with lookahead ' comprise the information
regime L ' . Thus, L 0 is the class of all traditional on-line algorithms.
Metrical task systems [3] are defined on some metric space M; a server
resides on some point of the metric space and can move from point to point.
Its goal is to process on-line a sequence of tasks cost c(T j ; a j )
of processing a task T j is determined by the task T j and the position a of the
server while processing the task. The total cost of processing the sequence is
the sum of the distance moved by the server plus the cost of servicing each
task
Theorem 2 For any metrical task system, R(L
there are metrical task systems for which R(L
Proof. Trivially the theorem holds for Assume that ' ? 0 and fix an
algorithm B in L ' . We shall define an on-line algorithm A without lookahead
whose cost on any sequence of tasks is at most 2' times the cost of B.
Algorithm A is a typical on-line algorithm in comparative analysis: It tries
to efficiently "simulate" the more powerful algorithm B. In particular, A
knows the position of B ' steps ago. In order to process the next task, A
moves first to B's last known position, and then processes the task greedily,
that is, with the minimum possible cost.
be a sequence of tasks and let b be the points where
algorithm B processes each task and a 1 ; a the corresponding points for
algorithm A. For simplicity, we define also points b negative
j's.
Then the cost of algorithm B is
and the cost of algorithm A is
Recall that in order to process the j-th task, algorithm A moves to B's last
known position b j \Gamma' and then processes the task greedily, that is, d(b
is the smallest possible. In particular,
?From this, the fact that costs are nonnegative and the triangle inequality
we get
Combining these with the triangle inequalities of the form
we get that the cost of algorithm A is at most
The last expression is times the cost of algorithm B.
For the converse, observe that when c(T
all triangle inequalities above hold as equalities then a comparative ratio of
can be achieved.
Of course, for certain task systems the comparative ratio may be less that
1. For the paging problem, it is ' + 1.
Theorem 3 For the paging problem
Proof. Let be an algorithm for the paging
problem in the class L ' , that is, with lookahead '. Without loss of generality
we assume that B moves its servers only to service requests. Consider the
following on-line algorithm A:
In order to service a request r, A moves a server that has not
been moved in the last n times such that the resulting configuration
is as close as possible to the last known configuration of
B.
Fix a worst request sequence ae and let A
the configurations of A and B that service ae. Without loss of generality, we
assume that A moves a server in each step. By definition, A services the t-th
request by moving a server not in B t\Gamman (unless A
We will first show by induction that A t and B t , differ in at
most n points: jB n. This is obviously true for t - n. Assume that
it holds for t\Gamman then clearly the statement holds, because in
each step the difference can increase by at most one. Otherwise, A services
the t-th request by moving the server from some point x, x 62 B t\Gamman . Observe
that A t can differ from B t in more than n points only if x 2 A
However, x can belong to B only if x was requested at least once
in the steps servers only to
service requests. Therefore, A moved a server at x in the last n steps and it
cannot move it again. Hence, A t and B t cannot differ in more than n points.
The theorem now follows from the observation that for every
moves of A there is a move of some server of B. The reason is this:
in the same configuration then A will converge to the same configuration
in at most n moves (recall that A moves a different server each
time).
4 Open problems
We introduced two refinements of competitive analysis, the diffuse adversary
model and comparative analysis. Both restrict the power of the adversary:
The first by allowing only certain input distributions and the second by
restricting the refinement of the adversary's information regime. In general,
we believe that the only natural way to deal with uncertainty is by designing
algorithms that perform well in the worst world which is compatible with
the algorithm's knowledge. There are numerous applications of these two
frameworks for evaluating on-line algorithms. We simply mention here two
challenging open problems.
The Markov diffuse adversary. Consider again the paging problem. Suppose
that the request sequence is the output sequence of an unknown Markov
chain (intuitively, the program generating the page requests) with at most
s states, which we can only partially observe via its output. That is, the
output f(q) of a state q of the unknown Markov process is a page in M . The
allowed distributions \Delta are now all output distributions of s-state Markov
processes with output. We may want to restrict our on-line algorithms to
ones that do not attempt to exhaustively learn the Markov process-one way
to do this would be to bound the length of the request sequence to O(s). We
believe that this is a useful model of paging, whose study and solution may
enhance our understanding of the performance of actual paging systems.
The power of vision. Consider two robots, one with vision ff (its visual
sensors can detect objects in distance ff) and the other with vision fi, fi ? ff.
We want to measure the disadvantage of the first robot in navigating or
exploring a terrain against the second robot. Naturally, comparative analysis
seems the most appropriate framework for this type of problems. Different
restrictions on the terrain and the objective of the robot result in different
problems but we find the following simple problem particularly challenging:
On the plain, there are n opaque objects. The objective of the robot is to
construct a map of the plain, i.e., to find the position of all n objects. We
ask what the comparative ratio R(V ff ; V fi ) for this problem is, where V ff and
V fi denote the information regimes of vision ff and fi, respectively.



--R

A new measure for the study of on-line algorithms
Competitive paging with locality of reference.
An optimal on-line algorithm for metrical task systems
The server problem and on-line games
Competitive paging algorithms.
Strongly competitive algorithms for paging with locality of reference.
Markov paging.
On the k-server conjecture
Beyond competitive analy- sis
Competitive algorithms for on-line problems
A strongly competitive randomized paging algorithm.
On the value of information.
Shortest paths without a map.
A statistical adversary for on-line algorithms
Memory versus randomization in on-line algorithms
Amortized efficiency of list update and paging rules.

--TR

--CTR
Peter Damaschke, Scheduling Search Procedures, Journal of Scheduling, v.7 n.5, p.349-364, September-October 2004
Marek Chrobak , Elias Koutsoupias , John Noga, More on randomized on-line algorithms for caching, Theoretical Computer Science, v.290 n.3, p.1997-2008, 3 January
Marcin Bienkowski, Dynamic page migration with stochastic requests, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
Peter Damaschke, Scheduling search procedures: The wheel of fortune, Journal of Scheduling, v.9 n.6, p.545-557, December  2006
Nicole Megow , Marc Uetz , Tjark Vredeveld, Models and Algorithms for Stochastic Online Scheduling, Mathematics of Operations Research, v.31 n.3, p.513-525, August 2006
Marek Chrobak, SIGACT news online algorithms column 8, ACM SIGACT News, v.36 n.3, September 2005
James Aspnes , Orli Waarts, Compositional competitiveness for distributed algorithms, Journal of Algorithms, v.54 n.2, p.127-151, February 2005
paging problem;online algorithms;competitive analysis;metrical task systems