This book, "Online Computation and Competitive Analysis," by Allan Borodin and Ran El-Yaniv, provides a comprehensive overview of online computation and competitive analysis. It covers various algorithms and models for solving online problems, with a focus on competitive analysis, which evaluates the performance of online algorithms relative to optimal offline algorithms. The book begins with an introduction to competitive analysis through the list accessing problem, discussing concepts like the potential function method, lower bounds, and list factoring. It then explores randomized algorithms for the same problem, including algorithms like BIT, RMTF, and COMB, and presents historical notes and open questions. The next chapters delve into paging algorithms, both deterministic and randomized. Deterministic algorithms include LFD, while randomized algorithms like MARK are discussed, along with lower bounds and the impact of different models on performance. The book also examines alternative paging models, such as the access graph model and distributional models, and explores game-theoretic foundations, including extensive and strategic forms of games, randomized strategies, and their applications to paging. The text then moves to request-answer games, competitive analysis and zero-sum games, metrical task systems, and the k-server problem. It discusses various algorithms for the k-server problem, including deterministic and randomized approaches, and explores load balancing, call admission, and circuit routing. The book also covers online search, trading, and portfolio selection, as well as decision theories and the competitive ratio. Throughout the book, the authors analyze the performance of online algorithms, compare them to optimal solutions, and explore theoretical and practical implications. The book concludes with a glossary, stochastic analyses, and proofs of various lemmas and theorems, providing a thorough resource for researchers and practitioners in the field of online computation and competitive analysis.This book, "Online Computation and Competitive Analysis," by Allan Borodin and Ran El-Yaniv, provides a comprehensive overview of online computation and competitive analysis. It covers various algorithms and models for solving online problems, with a focus on competitive analysis, which evaluates the performance of online algorithms relative to optimal offline algorithms. The book begins with an introduction to competitive analysis through the list accessing problem, discussing concepts like the potential function method, lower bounds, and list factoring. It then explores randomized algorithms for the same problem, including algorithms like BIT, RMTF, and COMB, and presents historical notes and open questions. The next chapters delve into paging algorithms, both deterministic and randomized. Deterministic algorithms include LFD, while randomized algorithms like MARK are discussed, along with lower bounds and the impact of different models on performance. The book also examines alternative paging models, such as the access graph model and distributional models, and explores game-theoretic foundations, including extensive and strategic forms of games, randomized strategies, and their applications to paging. The text then moves to request-answer games, competitive analysis and zero-sum games, metrical task systems, and the k-server problem. It discusses various algorithms for the k-server problem, including deterministic and randomized approaches, and explores load balancing, call admission, and circuit routing. The book also covers online search, trading, and portfolio selection, as well as decision theories and the competitive ratio. Throughout the book, the authors analyze the performance of online algorithms, compare them to optimal solutions, and explore theoretical and practical implications. The book concludes with a glossary, stochastic analyses, and proofs of various lemmas and theorems, providing a thorough resource for researchers and practitioners in the field of online computation and competitive analysis.