An Introduction to Online Computation: Determinism, by Dennis Komm

By Dennis Komm

This textbook explains on-line computation in several settings, with specific emphasis on randomization and suggestion complexity. those settings are analyzed for numerous on-line difficulties reminiscent of the paging challenge, the k-server challenge, task store scheduling, the knapsack challenge, the bit guessing challenge, and difficulties on graphs.

This ebook is acceptable for undergraduate and graduate scholars of desktop technological know-how, assuming a simple wisdom in algorithmics and discrete arithmetic. additionally researchers will locate this a useful reference for the new box of recommendation complexity.

Show description

Read or Download An Introduction to Online Computation: Determinism, Randomization, Advice PDF

Similar introduction books

The Future of Life-Cycle Saving and Investing: The Retirement Phase

In October 2008, approximately a hundred and fifty economists, actuaries, examine scientists, funding managers, and advisers met for 2 days at Boston collage to investigate the main urgent monetary concerns dealing with the "Boomer" new release in built international locations with getting older populations. The convention came about earlier than the election of Barack Obama as U.

Additional info for An Introduction to Online Computation: Determinism, Randomization, Advice

Example text

So far, the output of a fixed algorithm was fully determined by its strategy and the input, which is why we call such algorithms deterministic online algorithms. We may think of randomized online algorithms as online algorithms that toss a coin from time to time and use the outcome of this coin flip to produce the output. Formally, we need to introduce a random source which the algorithm may use; we neglect the potential difficulties of obtaining truly random numbers and simply suppose we have access to “real” randomness.

Here, an intuitive point of view might suggest more success; we learn from what happened so far, namely, we replace a page that was in some sense the least valuable up to now. Unfortunately, this strategy is not much better in the worst case. 23 Chapter 1. 7. Lfu is not competitive for paging. Proof. 6. For every ????′ , consider the instance ???? given by (????1 , ????1 , . . , ????1 , ????2 , ????2 , . . , ????2 , . . , ????????−1 , ????????−1 , . . , ????????−1 , ????????+1 , ???????? , . . , ????????+1 , ???????? ) ⏟ ⏞ ⏟ ⏞ ⏟ ⏞ ⏟ ⏞ ????′ requests ????′ requests ????′ requests 2(????′ −1) requests of length ???? := (????−1)????′ +2(????′ −1).

We first observe that both ????1 and ????Mark,1 start with the first request that causes a page fault. Every phase ???????? except the last one is by definition a maximum-length sequence of ???? distinct requests. Every requested page gets marked by Mark after being requested. If ???? distinct pages were requested, all pages in Mark’s cache are marked. With the (???? + 1)th distinct page ????′ being requested since the beginning of ???????? , a new phase ????????+1 starts. In this time step, Mark also starts a new phase ????Mark,????+1 , as there is no unmarked page left in its cache to replace with ????′ .

Download PDF sample

An Introduction to Online Computation: Determinism, by Dennis Komm
Rated 4.78 of 5 – based on 19 votes