Kirjahaku

Online algorithms are a rich area of research with widespread applications in scheduling, combinatorial optimization, and resource allocation problems. This lucid textbook provides an easy but 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. The book starts with classical online paradigms like the ski-rental, paging, list-accessing, bin packing, where performance of online 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. 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.

This book discusses the theoretical limits of information transfer in random wireless networks or ad hoc networks, where nodes are distributed uniformly in space and there is no centralised control. It provides a detailed analysis of the two relevant notions of capacity for random wireless networks – transmission capacity and throughput capacity. The book starts with the transmission capacity framework that is first presented for the single-hop model and later extended to the multi-hop model with retransmissions. Reusing some of the tools developed for analysis of transmission capacity, a few key long-standing questions about the performance analysis of cellular networks are also provided for the benefit of students. The discussion goes further into the concept of hierarchical co-operation that allows throughput capacity to scale linearly with the number of nodes. The author finally discusses the concept of hierarchical co-operation that allows throughput capacity to scale linearly with the number of nodes.