By Dennis Komm

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

This booklet 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 beneficial reference for the hot box of recommendation complexity.

Show description

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

Best introduction books

Introduction to Hybrid Vehicle System Modeling and Control

This can be an engineering reference publication on hybrid automobile approach research and layout, an outgrowth of the author's significant paintings in learn, improvement and construction on the nationwide examine Council Canada, Azure Dynamics and now normal vehicles. it truly is an irreplaceable instrument for assisting engineers improve algorithms and achieve a radical knowing of hybrid automobile platforms.

Elliptic curves and their applications to cryptography : an introduction

Due to the fact that their invention within the past due seventies, public key cryptosystems became an necessary asset in setting up deepest and safe digital communique, and this desire, given the great progress of the net, is probably going to proceed becoming. Elliptic curve cryptosystems signify the state-of-the-art for such structures.

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

Sample text

Formally, phase ????Fifo,???? ends immediately after Fifo made (???? − 1)???? + 1 page faults. The last phase may be shorter. Use this phase partition to show that Fifo is ????-competitive. Does your proof show that Fifo is strictly ????-competitive? 10. Fifo experiences a phenomenon that is known as Bélády’s anomaly, which states that there are instances on which Fifo causes more page faults if it has a larger cache. Find such an instance. Hint. It suffices to consider two cache sizes 3 and 4 and a total number of nine pages.

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). In the first (????−1)????′ time steps, no online algorithm causes a page fault, and after that, all pages in the cache have been requested ????′ times except for ???????? .

There may be more than one such page, in which case Opt chooses the page whose first request is the latest among all such pages (Opt therefore implements the offline strategy Lfd). We can use the same argument for any other phase ???????? with 2 ≤ ???? ≤ ???? . The only difference is that Opt does not surely cause a page fault in the first time step ????(????−1)????+1 of this phase, but it may cause a page fault later or even not at all. However, whenever a page fault occurs, by the same reasoning as for phase ????1 , there must be some page that is not requested anymore during phase ???????? and that may therefore be safely removed from the cache.

Download PDF sample

Rated 4.74 of 5 – based on 28 votes