Loading...
Please wait, while we are loading the content...
Similar Documents
Competitive Analysis of Paging: A Survey (1996)
| Content Provider | CiteSeerX |
|---|---|
| Author | Irani, Sandy |
| Description | . This paper is a survey of competitive analysis of paging. We present proofs showing tight bounds for the competitive ratio achievable by any deterministic or randomized online algorithm. We then go on to discuss variations and refinements of the competitive ratio and the insights they give into the paging problem. Finally, we variations to the online paging problem to which competitive analysis has been applied. 1 Introduction The paging problem has inspired several decades of theoretical and applied research and has now become a classical problem in computer science. This is due to the fact that managing a two level store of memory has long been, and continues to be, a fundamentally important problem in computing systems. The paging problem has also been one of the cornerstones in the development of the area of online algorithms. Starting with the seminal work of Sleator and Tarjan which initiated the recent interest in the competitive analysis of online algorithms, the paging probl... |
| File Format | |
| Language | English |
| Publisher Date | 1996-01-01 |
| Publisher Institution | In Proceedings of the Dagstuhl Seminar on Online Algorithms, Dagstuhl |
| Access Restriction | Open |
| Subject Keyword | Level Store Several Decade Paging Probl Randomized Online Algorithm Tight Bound Competitive Ratio Recent Interest Important Problem Paging Problem Computer Science Classical Problem Online Algorithm Seminal Work Competitive Analysis |
| Content Type | Text |
| Resource Type | Article |
