The book "Online Computation and Competitive Analysis" by Allan Borodin and Ran El-Yaniv provides a comprehensive overview of competitive analysis and randomized algorithms, with a focus on the list accessing problem. It covers various topics including: 1. **Introduction to Competitive Analysis**: Discusses the basic ideas, terminology, and the Sleator–Tarjan result, along with the potential function method and lower bounds. 2. **Introduction to Randomized Algorithms**: Explores the competitive ratio of randomized algorithms, the BIT algorithm, and the RMTF algorithm, which compares barely random and random approaches. 3. **Paging**: Analyzes deterministic and randomized paging algorithms, including the $(h, k)$-paging problem, optimal offline algorithms, and the competitiveness of LRU, CLOCK, FIFO, and FWF. 4. **Alternative Paging Models**: Introduces the access graph model, dynamic access graphs, and distributional paging models. 5. **Game Theoretic Foundations**: Covers extensive and strategic games, randomized strategies, and their applications to paging and competitive analysis. 6. **Request-Answer Games**: Discusses request-answer games, randomized adversaries, and their relations. 7. **Competitive Analysis and Zero-Sum Games**: Examines two-person zero-sum games, generalizations of the minimax theorem, and Yao's principle. 8. **Metrical Task Systems**: Formulates task systems, presents competitive algorithms, and discusses lower bounds. 9. **The k-Server Problem**: Formulates the model, discusses basic aspects, and presents efficient algorithms for specific cases. 10. **Randomized k-Server Algorithms**: Introduces oblivious adversaries, lower bounds, and randomized algorithms like the harmonic random walk. 11. **Load Balancing**: Discusses the problem, online algorithms for permanent and temporary jobs, and bin packing. 12. **Call Admission and Circuit Routing**: Focuses on throughput maximization, disjoint paths, and routing on optical networks. 13. **Search, Trading, and Portfolio Selection**: Covers online search, trading, and portfolio selection, including statistical adversaries and Bayesian approaches. 14. **Decision Theories and the Competitive Ratio**: Explores decision-making under uncertainty, risk, and Bayesian approaches, and characterizes the competitive ratio. The book also includes historical notes, open questions, and detailed proofs for various algorithms and theorems.The book "Online Computation and Competitive Analysis" by Allan Borodin and Ran El-Yaniv provides a comprehensive overview of competitive analysis and randomized algorithms, with a focus on the list accessing problem. It covers various topics including: 1. **Introduction to Competitive Analysis**: Discusses the basic ideas, terminology, and the Sleator–Tarjan result, along with the potential function method and lower bounds. 2. **Introduction to Randomized Algorithms**: Explores the competitive ratio of randomized algorithms, the BIT algorithm, and the RMTF algorithm, which compares barely random and random approaches. 3. **Paging**: Analyzes deterministic and randomized paging algorithms, including the $(h, k)$-paging problem, optimal offline algorithms, and the competitiveness of LRU, CLOCK, FIFO, and FWF. 4. **Alternative Paging Models**: Introduces the access graph model, dynamic access graphs, and distributional paging models. 5. **Game Theoretic Foundations**: Covers extensive and strategic games, randomized strategies, and their applications to paging and competitive analysis. 6. **Request-Answer Games**: Discusses request-answer games, randomized adversaries, and their relations. 7. **Competitive Analysis and Zero-Sum Games**: Examines two-person zero-sum games, generalizations of the minimax theorem, and Yao's principle. 8. **Metrical Task Systems**: Formulates task systems, presents competitive algorithms, and discusses lower bounds. 9. **The k-Server Problem**: Formulates the model, discusses basic aspects, and presents efficient algorithms for specific cases. 10. **Randomized k-Server Algorithms**: Introduces oblivious adversaries, lower bounds, and randomized algorithms like the harmonic random walk. 11. **Load Balancing**: Discusses the problem, online algorithms for permanent and temporary jobs, and bin packing. 12. **Call Admission and Circuit Routing**: Focuses on throughput maximization, disjoint paths, and routing on optical networks. 13. **Search, Trading, and Portfolio Selection**: Covers online search, trading, and portfolio selection, including statistical adversaries and Bayesian approaches. 14. **Decision Theories and the Competitive Ratio**: Explores decision-making under uncertainty, risk, and Bayesian approaches, and characterizes the competitive ratio. The book also includes historical notes, open questions, and detailed proofs for various algorithms and theorems.