Online Algorithms

This textbook provides a rigorous introduction to online algorithms for graduate and senior undergraduate students. In-depth coverage of most of the important topics is presented with special emphasis on elegant analysis. A wide range of solved examples and practice exercises are included, allowing hands-on exposure to the basic concepts.

"Online algorithms are an optimization paradigm where input is revealed sequentially and an algorithm has to make irrevocable decisions using only causal information. This is a growing area of research with great interest from the theoretical computer science community, having significant practical applications in operations research, big data analysis, design of communication networks, and so on. There are many different mathematical techniques that have been developed to analyse online algorithms, suchas potential function arguments, primal-dual methods, and Yao''s principle, to name a few. This textbook presents an easy but rigorous introduction to online algorithms for students. It starts with classical online paradigms like the ski-rental, paging, list-accessing, and bin packing, where performance of the algorithms is studied under the worst-case input and moves on to newer paradigms like ''beyond worst case'', where online algorithms are augmented with predictions using machine learning algorithms. Several other popular online problems, such as metrical task systems, which includes the popular k-server problem as a special case, secretary, knapsack, bipartite matching, load balancing. scheduling to minimize flow-time, facility location, k-means clustering, travelling salesman, are also covered. A very useful technique for analysing online algorithms called the primal-dual schema is also included together with its application for multiple problems. The book goes on to cover multiple applied problems such as routing in communication networks, server provisioning in cloud systems, communication with energy harvested from renewable sources, and sub-modular partitioning. Finally, a wide range of solved examples and practice exercises are included, allowing hands-on exposure to the concepts. Each exercise has been broken down into simpler parts to provide a clear path towards the solution"--