Description
An Introduction to Online Computation, 1st ed. 2016
Determinism, Randomization, Advice
Texts in Theoretical Computer Science. An EATCS Series
Author: Komm Dennis
Language: English
Subjects for An Introduction to Online Computation:
Publication date: 11-2016
Support: Print on demand
Publication date: 06-2018
Support: Print on demand
Description
/li>Contents
/li>Biography
/li>Comment
/li>
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.
Introduction.- Randomization.- Advice Complexity.- The k-Server Problem.- Job Shop Scheduling.- The Knapsack Problem.- The Bit Guessing Problem.- Problems on Graphs.
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.
