**Allan Borodin and Ran El-Yaniv**

The List Accessing Problem

**1.1 Basic ideas and terminology
**

1.1.2 The competitive ratio and competitiveness

1.1.3 Games and adversaries

1.2 The list accessing problem

1.2.1 Models

1.2.2 Three Classical list accessing algorithms

1.2.3 On free and paid transpositions

1.3 The Sleator-Tarjan result

1.4 The potential function method

First style: Amortized costs

Second style: Interleaving moves

1.5 Some lower bounds

Lower bound for TRANS

Lower bound for FC

1.6 The list factoring technique

1.6.1 A Phase partitioning technique

1.7 Historical notes and open questions

1.7.1 Open questions

The List Accessing Problem

**2.1 The competitive ratio of randomized algorithms
2.2 Algorithm BIT
2.3 Algorithm RMTF: barely random vs. random
2.4 List factoring - phase partitioning revisited
2.5 COMB: an $8/5$-competitive algorithm
2.6 Historical notes and open questions
2.6.1 Open questions **

**Chapter 3 Paging: Deterministic Algorithms
**

**3.1 The $(h,k)$-paging problem
3.2 Some paging algorithms
3.3 LFD - and optimal offline paging algorithm
3.4 Marking and Conservative algorithms and the competitiveness
of LRU, FIFO, CLOCK and
FWF
3.4.1 Marking algorithms
3.4.2 Conservative algorithms
3.4.3 A lower bound
3.5 LIFO and LFU are not competitive
3.6 The full access cost model
3.7 Theory vs. practice
3.8 Historical notes and open questions
3.8.1 Open questions **

**Chapter 4 Paging: Randomized algorithms **

**4.1 Randomized competitive analysis
4.1.1 Adversary models
4.2 The competitiveness of Random
4.3 The Marking algorithm
4.4 A lower bound for randomized paging algorithms
4.5 Historical notes and open questions
4.5.1 Open questions **

Beyond Pure Competitive Analysis

**5.1 The restricted Bayesian compromise
5.2 The Access Graph Model
5.2.1 FIFO in the access graph
model
5.2.2 LRU in the access graph
model
5.2.3 FAR: A uniformly competitive
paging algorithm
5.3 Experimental studies relating to access graph mode
l 5.4 Distributional paging models
5.4.1 The Markov chain model
5.4.2 A more general distributional
model
5.4.3 A diffuse adversary
5.5 Prefectching models
5.6 Historical notes and open questions
5.6.1 Open questions**

**6.1 Games in extensive and strategic forms
6.1.1 Games in extensive form
6.1.2 Games in strategic form
6.1.3 Transformations between
strategic and extensive forms
6.2 Randomized strategies: mixed, behavioral and general
6.2.1 Mixed strategies
6.2.2 Behavioral strategies
6.2.3 General strategies
6.3 Equivalence theorems for linear games and games of perfect recall
6.4 Implications for competitive analysis
6.5 Historical notes and open questions
6.5.1 Open questions **

**7.1 Request-answer games
Online
algorithms
Adversaries
and their interaction with algorithms
The
competitive ratio
Request
answer games and profit maximization problems
7.2 Randomized adversaries
7.3 Relating the adversaries
7.4 The request answer games framework - A critical examination
7.5 Historical notes and open questions
7.5.1 Open qustions **

**8.1 Two-person zero-sum games
8.2 On Generalizations of the minimax theorem for infinite games
8.3 Yao's principle: a technique for obtaining lower bounds
8.3.1 Yao's principle for profit
maximization problems
8.3.2 Yao's principle for cost
minimization problems
8.4 Paging revisited
8.5 Historical notes and open questions
8.5.1 Open questions**

**9.1 Formulation of (Metrical) Task Systems
9.1.1 Continuous time algorithms
9.1.2 Nearly oblivious and traversal
algorithms
9.2 An $8(K-1)$-competitive traversal algorithm
9.3 Cruel adversaries and a $2K-1$ lower bound
9.3.1 Cruel adversaries
9.3.2 A lower bound
9.4 An optimal work function MTS algorithm
9.5 Randomized algorithm for a uniform MTS
9.6 Historical notes and open questions
9.6.1 Open questions**

**10.1 The formulation of the model
10.2 Some basic aspects of the $k$-server problem
10.2.1 The optimal
offline algorithm
10.2.2 The greedy
policy is not competitive
10.2.3 Lazy algorithms
10.2.4 Some generalizations
and variants of the server problem
10.2.5 The $k$-server
conjecture
10.3 A deterministic lower bound
10.4 $k$-servers on a line and a tree
10.4.1 The line algorithm
10.4.2 The tree algorithm
10.4.3 Some applications
of the tree algorithm
10.5 A 3-competitive 2-server algorithm for Euclidean spaces
10.6 Balancing algorithms
10.7 The $k$-server work function algorithm
10.7.1 Work functions
for the $k$-server problem
10.7.2 The online
$k$-server work function algorithm
10.7.3 Analysis of
algorithm WFA
10.8 On generalizations of the $k$-server conjecture that fail
10.8.1 The $(h,k)$-server
problem
10.8.2 Asymmetric
spaces
10.9 Historical notes and open questions
10.9.1 Open questions
**

**11.1 Two randomized $k$-server algorithms for the circle
11.1.1 A $2k$-competitive
algorithm
11.1.2 A circle algorithm
with sub-linear ratio
11.2 A lower bound against an adaptive online adversary
11.3 The cat and rat game and applications to randomized $k$-server algorithms
11.4 The Harmonic algorithm
11.5 Randomized algorithms for Resistive spaces
11.6 Historical notes and open questions
11.6.1 Open questions**

**12.1 Introduction
12.1.1 Load balancing
vs. call admission
12.1.2 Load balancing
variations
12.1.3 Different
machine models
12.1.4 Scalable problems
12.2 Online algorithms for load balancing of permanent jobs
12.2.1 Identical
machines
12.2.2 The restricted
machines model
12.2.3 The related
machines case
12.3 Formulating the Machine Assignment Problem as a Generalized
Virtual Circuit Routing
Problem
12.4 Load Balancing of Temporary Jobs
12.4.1 Known durations
12.4.2 Unknown durations
12.5 Historical notes and open problems
12.5.1 Open questions
**

**13.1 Specifying the problem
13.2 Throughput maximization for permanent calls in
networks with large
edge capacities
13.3 Throughput maximization for limited duration calls
13.4 Experimental results
13.5 Call admission for particular networks : The disjoint paths problem
13.5.1 Routing on
the line
13.5.2 Routing on
trees
13.5.3 Routing on
arrays
13.6 The disjoint paths problem: a lower bound for a difficult network
13.7 Routing on optical networks
13.8 Path colouring for particular networks
13.8.1 Path coloring
on the line
13.8.2 Path colouring
on trees
13.8.3 Path colouring
on arrays
13.9 A lower bound for path colouring on the brick wall graph
13.10 Historical notes and open problems
13.10.1
Open questions**

**14.1 Online search and one-way trading
14.1.1 The relationship
between randomized search and
one-way
trading algorithms
14.1.2 Competitive
search algorithms
14.1.3 The ``threat-based''
policy
14.2 Online portfolio selection and two-way trading
14.2.1 Buy-and-hold
vs. Market timing
14.2.2 Constant rebalanced
algorithms
14.3 Statistical adversaries and ``money-making'' algorithms
14.3.1 The $(n,\phi
)$-adversary
14.3.2 Weaker statistical
adversaries and the general ``money-making'' scheme
14.4 The fixed fluctuation model
14.4.1 On the fixed
fluctuation model and time scaling
14.4.2 The optimal
online algorithm against the $(\alpha ,n,k)$-adversary
14.4.3 On the empirical
performance of MM
14.4.4 Binomial risk-neutral
pricing and adversarial analysis
14.5 Online portfolio selection
14.5.1 The family
of $\mu $-weighted portfolio selection algorithms
14.5.2 The uniform-weighted
algorithm
14.5.3 Dirichlet-weighted
algorithms
14.5.4 Extremal mixture
algorithms
14.5.5 Portfolio
selection with side information
14.6 Historical notes and open questions
14.6.1 Open questions
**

Under Uncertainty

**15.1 Certainty, uncertainty, risk and strict uncertainty
15.1.1 A simple decision
theoretic model
15.1.2 Descriptive
theories vs. prescriptive theories
15.1.3 Certainty
and uncertainty
15.2 Decision making under risk
15.2.1 Utility functions
and attitudes toward risk
15.2.2 von Neumann-Morgenstern
expected utility theory
15.2.3 The Allais
paradox and other violations of the expected utility theory
15.2.4 Other approaches
to decision making under risk
15.3 Decision making under strict uncertainty
15.3.1 Some criteria
for strict uncertainty
15.3.2 Some problematic
examples
15.3.3 Algorithmic
decision problems
15.3.4 Some classifications
of problems
15.3.5 Decision criteria
for algorithmic decision problems
under
strict uncertainty
15.4 The competitive ratio axioms
15.5 Characterization of the competitive ratio
15.6 Characterizations of the classical criteria for strict uncertainty
15.6.1 Characterization
of the minimax cost
15.6.2 Characterization
of the minimax regret
15.6.3 Characterizations
of the principle of insufficient reason
15.6.4 Characterizations
of the pessimism-optimism index
15.7 An example - the leasing problem
15.7.1 The principle
of Insufficient Reason
15.7.2 The minimax
regret
15.7.3 The competitive
ratio
15.7.4 The pessimism-optimism
index
15.7.5 The minimax
cost
15.8 Bayesian approaches for decision making under uncertainty
15.9 Historical notes and open questions
15.9.1 Open questions
**

**C.1 Renewal processes
C.2 Wald's equation
C.3 The Elementary Renewal Theorem **

**D.1 Short distance calls
D.2 Long distance calls **

Copyright ©1996 A. Borodin and R. El-Yaniv