An Introduction to Online Computation
Springer International Publishing (Verlag)
978-3-319-82653-0 (ISBN)
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.
Dr. Dennis Komm is a lecturer in the Chair of Information Technology and Education at ETH Zürich. His research interests include approximation algorithms for hard optimization problems, re-optimization of optimization problems, and advice complexity in different setups and environments.
Introduction.- Randomization.- Advice Complexity.- The k -Server Problem.- Job Shop Scheduling.- The Knapsack Problem.- The Bit Guessing Problem.- Problems on Graphs.
"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)
| Erscheint lt. Verlag | 28.6.2018 |
|---|---|
| Reihe/Serie | Texts in Theoretical Computer Science. An EATCS Series |
| Zusatzinfo | XV, 349 p. 58 illus. |
| Verlagsort | Cham |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 563 g |
| Themenwelt | Informatik ► Theorie / Studium ► Algorithmen |
| Mathematik / Informatik ► Mathematik ► Analysis | |
| Schlagworte | Advice Complexity • Computational Complexity • online algorithms • Oracles • Paging Problem • randomized algorithms |
| ISBN-10 | 3-319-82653-0 / 3319826530 |
| ISBN-13 | 978-3-319-82653-0 / 9783319826530 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
