More on weighted servers or FIFO is better than LRU

Epstein, Leah; Imreh, Csanád; van Stee, Rob; Diks, Krzysztof; Rytter, Wojciech

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

More on weighted servers or FIFO is better than LRU

MPS-Authors

Imreh, Csanád
Max Planck Society;

/persons/resource/persons45543

van Stee, Rob
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

Epstein, L., Imreh, C., & van Stee, R. (2002). More on weighted servers or FIFO is better than LRU. In Mathematical Foundations of Computer Science 2002: 27th International Symposium, MFCS 2002 (pp. 257-268). Berlin, Germany: Springer.

Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-2FF4-3

Abstract

We consider a generalized 2-server problem on the uniform space in which servers have different costs. Previous work focused on the case where the ratio between these costs was very large. We give results for varying ratios. For ratios below 2.2, we present an optimal algorithm which is trackless. %Furthermore, our algorithm is trackless, %which means that it is restricted from storing %explicitly points from the metric space. We present a general lower bound for trackless algorithms depending on the cost ratio, proving that our algorithm is the optimal trackless algorithm up to a constant factor for any cost ratio. The results are extended for the case where we have two sets of servers with different costs.