MPI für Informatik / Algorithms and Complexity Group |
|More on weighted servers or FIFO is better than LRU|
|Authors:||Epstein, Leah; Imreh, Csanád; van Stee, Rob|
|Editors:||Diks, Krzysztof; Rytter, Wojciech|
|Place of Publication:||Berlin, Germany|
|Date of Publication (YYYY-MM-DD):||2002|
|Title of Proceedings:||Mathematical Foundations of Computer Science 2002 : 27th International Symposium, MFCS 2002|
|Title of Series:||Lecture Notes in Computer Science|
|Place of Conference/Meeting:||Warsawa-Otwock, Poland|
|(Start) Date of Conference/Meeting|
|Review Status:||not specified|
|Intended Educational Use:||No|
|Abstract / Description:||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.
|Last Change of the Resource (YYYY-MM-DD):||2003-08-28|
|External Publication Status:||published|
|Communicated by:||Kurt Mehlhorn|
|Affiliations:||MPI für Informatik/Algorithms and Complexity Group|