Chapter 1 explains what an on-line problem is and defines the competitive ratio of an
on-line algorithm -- the basic measure of algorithm performance in competitive analysis,
defined as the worst-case ratio (over all inputs) of the cost incurred by the algorithm on an
input to the cost incurred by the optimal solution for that input.
Chapter 2 expands on Chapter 1, presenting and analyzing 3 randomized on-line strategies,
and general lower bounds, for the list-accessing problem.
Chapter 3 introduces the paging problem -- in response to a sequence of requests for
items, one must maintain a fixed-size cache k of the items. The cost of each request is 1
if the requested item is not in the cache and 0 otherwise. Six deterministic algorithms are
analyzed -- 4 are shown k-competitive, 2 are shown not to be competitive at all. The ratio of
k is shown to be the best possible for any online deterministic strategy. Some experimental
results are presented.
Chapter 4 expands on Chapter 3, presenting and analyzing 2 of the easier-to-analyze
randomized online paging algorithms (RANDOM and MARK; the optimally competitive
algorithms PARTITION and EQUITABLE are not presented in detail). A general lower
bound for randomized online algorithms is also presented.
Chapter 5 presents some of the variants of standard competitive analysis for paging,
focusing mainly on the access-graph model, but also stating some basic results in the Markovchain
and diffuse-adversary models. These variants are motivated by the observation that
in the standard model, the theoretical competitive ratios of (even optimal) online strategies,
especially deterministic ones, are much higher than is typically observed in practice. Some
preliminary empirical results are presented.
Chapter 6 summarizes background material in basic game theory: extensive and strategic
representations of 2-person, zero-stun games; games of complete vs. incomplete information;
various kinds of randomized strategies (mixed, behavioral, and general, linear games
and games of perfect recall). The chapter presents one application of game theory, to memoryless
randomized paging algorithms (memoryless means that each decision of which depends
only on the current request and cache contents).
Chapter 7 presents request-answer games, a general class of online problems including
paging and list-accessing. For randomized strategies, there are at least three reasonable
ways to define the competitive ratio -- (1) using an oblivious adversary, who knows what
the on-line algorithm is but not the specific random choices it makes as it proceeds (this
is the most commonly used model, and the easiest for the on-line algorithm), (2) using
an adaptive-offline adversary, who knows the random choices made by the algorithm up to
the current time and can use this information as it builds the request sequence (this is the
hardest for the online algorithm), or (3) using an adaptive-online adversary, a limited form
of the adaptive~offline adversary that must itself decide how to service each request as it is
generated (not knowing the future random choices of the algorithm). Chapter 7 presents
the following results: for any request-answer game, if there are online algorithms that are,
respectively, a- and b-competitive in models (1) and (2), then there is an online algorithm
that is ab-competitive in model (3). Furthermore, randomization does not help the online
algorithm in model (3).
Chapter 8 continues the study of game theory by focusing on yon Neumann and Morgenstem's
minimax theorem for 2-person zero-sum games. The authors discuss generalizations
of the theorem to infinite games, and how the theorem implies a method (often called Yao's
principle) for obtaining lower bounds on the complexity (in this case the competitive ratio) of
randomized strategies. A single application (obtaining a lower bound for randomized paging
algorithms) is presented.
Chapter 9, metrical task systems (MTS) are considered. This is another general
abstraction for many on-line problems, generalizing paging but only some versions of the
list-accessing problem. An O(N)-competitive deterministic algorithm is analyzed, where N
is the number of states of the MTS. Note that for paging, N : (:), where n is the number
of distinct items and k is the size of the cache. A more complicated but optimally competitive
work-function based algorithm is also presented. An O(log N)-competitive randomized
algorithm for uniform MTS is presented, followed by a relatively complicated but seminal
poly-logarithmically-competitive randomized algorithm for arbitrary MTS's. Both analyses
are given in the chapter.
The infamous k-server problem is the subject of Chapter 10. The k-server conjecture
is that the optimal competitive ratio for any deterministic on-line algorithm for the k-server
problem is k. A lower bound of k was known in 1985, but no reasonable upper bound was
shown for any on-line algorithm until a decade later.
The problem is to dynamically locate k servers in a metric space in response to requests
for service occurring at locations in the space. At each request, some server must be moved
to the location of the request, at a cost equal to the distance from the previous location of
the server to the requested location. Paging is the special case when the pairwise distances
are each 1.
The k-competitive tree algorithm and its elegant analysis are presented for the special
case when the metric space corresponds to a tree with weighted edges. Two other special
cases are presented. Finally, the authors give the relatively involved analysis of the workfunction
algorithm (the result that essentially settled the problem) showing that it is (2k- 1)-
competitive for the general problem.
Chapter 11 discusses and analyses randomized algorithm.q for special cases of the kserver
problem: when the metric space is the circle; and when the metric space is resistive, in
which case the HARMONIC algorithm (move a server with probability inversely proportional
to its distance to the request) is shown to be k-competitive.
Chapter 12 concerns load-balancing/packing type problems, including: scheduling on
restricted, related, and unrelated machines; virtual circuit routing in graphs (a sort of on-line
multicommodity flow or call-scheduling problem) and variants; bin packing (4 pp., covering
2 deterministic on-line strategies).
Chapter 13 continues in the vein of Chapter 12, presenting algorithms for call admission
and circuit routing, on-line disjoint paths on specific networks, and optical network routing
(an extension of disjoint paths). Some empirical results are presented.
Portfolio selection (making money!) is the topic of Chapter 14. The first problem
considered is one-wall trading, in which a fixed amount of one currency must be converted
to another currency over a period of time in which the exchange rate varies in an interval
[m, M]. (Conversion back to the original currency is not allowed.) Randomization is shown
not to help, and the optimal competitive ratio is shown to be O(log(M/m)).
The second problem considered is portfolio 8election, in which an initial amount of cash
(not cache!) is used to buy and sell securities whose prices rise and fall over a specified time
period. Two offline algorithms are considered (buy and hold one stock, rebalance to keep a
relative total values of each type of stock constant) and compared on empirical data. Various
online algorithms that achieve competitive ratios of ~o(m) with respect to the optimal of]tine
strategy based on constant rebalancing are described and analyzed (these analyses appear
fairly technical).
The third problem considered is two-way trading -- the special case of portfolio selection
when there are just two securities available. Competitive ratios (versus the optimal of Hine)
in this model are shown to be very bad -- exponential in n (the number of trading periods).
Restrictions on the adversary are considered, and some empirical results are presented.
Chapter 15 concludes the book with a discussion of competitive analysis in the general
context of decision making under uncertainty. The general question is how, for a given problem,
to order the online algorithms in order of preference (independent of particular inputs).
Competitive analysis is one way to do this, but the general problem has been considered
extensively in the past and many other criteria have been studied. Quoting from the book:
"A decision making approach very similar to competitive analysis was known almost 50 years
ago. However, .for the most part is was superseded by the 'Bayesian approach,' which e~olved
to be the main tool .for most online applications in economics and finance, statistics, and
operations research."
The chapter continues with an axiomatic approach to various decision-making criteria
(by a "criteria" we mean a way of ordering the online algorithms by preference; competitive
analysis is such a criterion). For example, one might naturally restrict oneself to criteria
that do not distinguish between algorithms that are essentially isomorphic in various natural
ways. Going further, if one algorithm performs better on every input than another algorithm,
surely any reasonable criterion should prefer the former algorithm. By building up natural
properties like these, one can eventually pin down a specific criterion. A natural question
is which sets of properties lead to which criteria. This is presumably not just of academic
interest, because in any given application one might suspect that certain properties are more
important than others. After developing this general approach, the authors give some specific
examples of criteria and how they apply to a simple on-line problem. The chapter ends with •
a discussion of utility theory.