Home News About Us Contact Contributors Disclaimer Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Display Documents



ID: 202083.0, 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
Language:English
Publisher:Springer
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
Start Page:257
End Page:268
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Warsawa-Otwock, Poland
(Start) Date of Conference/Meeting
 (YYYY-MM-DD):
2002-08-26
Review Status:not specified
Audience:Experts Only
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
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:MPI für Informatik/Algorithms and Complexity Group
Identifiers:LOCALID:C1256428004B93B8-07DC6BF42FF3A0C6C1256C3700449651-...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.