Buying a Constant Competitive Ratio for Paging

TitleBuying a Constant Competitive Ratio for Paging
Publication TypeConference Paper
Year of Publication2001
AuthorsCsirik J, Imreh C, Noga J, Seiden SS, Woeginger GJ
Editorder Heide FMeyer auf
Conference NameAlgorithms –- ESA 2001
PublisherSpringer Berlin Heidelberg
Place PublishedBerlin, Heidelberg
ISBN Number978-3-540-44676-7

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.