This textbook explains online computation in different settings, with particular emphasis on randomization and advice complexity. These settings are analyzed for various online problems such as the paging problem, the k-server problem, job shop scheduling, the knapsack problem, the bit guessing problem, and problems on graphs.
This book is appropriate for undergraduate and graduate students of computer science, assuming a basic knowledge in algorithmics and discrete mathematics. Also researchers will find this a valuable reference for the recent field of advice complexity.
"This book is about online algorithms for optimization problems. ? The book can be used as a textbook on the undergraduate level. ? The book can also be used for self-study and as a reference. Its strength in this regard is enhanced by the historical notes at the end of each chapter and a comprehensive bibliography." (Bogdan S. Chlebus,Mathematical Reviews, March, 2018)
"This text is an important contribution to the field of online algorithms. ? Without a doubt, this text is a must-read for anyone seriously pursuing the analysis of algorithms, particularly online versions of those algorithms." (Michael Goldberg and R. Goldberg, Computing Reviews, October, 2017)
