Buying a Constant Competitive Ratio for Paging
| Title | Buying a Constant Competitive Ratio for Paging |
| Publication Type | Conference Paper |
| Year of Publication | 2001 |
| Authors | Csirik J, Imreh C, Noga J, Seiden SS, Woeginger GJ |
| Editor | der Heide FMeyer auf |
| Conference Name | Algorithms –- ESA 2001 |
| Pagination | 98–108 |
| Publisher | Springer Berlin Heidelberg |
| Place Published | Berlin, Heidelberg |
| ISBN Number | 978-3-540-44676-7 |
| Abstract | We consider a variant of the online paging problem where the online algorithm may buy additional cache slots at a certain cost. The overall cost incurred equals the total cost for the cache plus the number of page faults. This problem and our results are a generalization of both, the classical paging problem and the ski rental problem. |