An Introduction to Online Computation Determinism, Randomization, Advice /

• Main Author: Komm, Dennis (Author)
• Corporate Author: SpringerLink (Online service)
• Format: Electronic eBook
• Language: English
• Published: Cham : Springer International Publishing : Imprint: Springer, 2016.
• Series: Texts in Theoretical Computer Science. An EATCS Series,
• Subjects: Computer science.; Computers.; Algorithms.; Computer Science.; Theory of Computation.

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 prob...

Table of Contents:

• Introduction
• Randomization
• Advice Complexity
• The k-Server Problem
• Job Shop Scheduling
• The Knapsack Problem
• The Bit Guessing Problem
• Problems on Graphs.