Online Computation and Competitive Analysis

Allan Borodin and Ran El-Yaniv

Chapter 0 Preface

Chapter 1 Introduction to Competitive Analysis:
The List Accessing Problem

1.1 Basic ideas and terminology
       1.1.1 Offline and online optimization problems
       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

Chapter 2 Introduction to Randomized Algorithms:
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

Chapter 5 Alternative Models for Paging:
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

Chapter 6 Game-Theoretic Foundations

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

Chapter 7 Request-Answer Games

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

Chapter 8 Competitive Analysis and Zero-Sum Games

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

Chapter 9 Metrical Task systems

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

Chapter 10 The $k$-Server Problem

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

Chapter 11 Randomized $k$-server Algorithms

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

Chapter 12 Load-Balancing

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

Chapter 13 Call Admission and Circuit-Routing

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

Chapter 14 Search, Trading and Portfolio Selection

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

Chapter 15 Competitive Analysis and Decision Making
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