Loading...
Please wait, while we are loading the content...
Similar Documents
Competitive k-Server Algorithms (1990)
| Content Provider | CiteSeerX |
|---|---|
| Author | Ravid, Yiftach Fiat, Amos Rabani, Yuval |
| Abstract | In this paper we give deterministic competitive k-server algorithms for all k and all metric spaces. This settles the k-server conjecture [MMS] up to the competitive ratio. The best previous result for general metric spaces was a 3-server randomized competitive algorithm [BKT] and a non-constructive proof that a deterministic 3-server competitive algorithm exists [BBKTW]. The competitive ratio we can prove is exponential in the number of servers. Thus, the question of the minimal competitive ratio for arbitrary metric spaces is still open. 1 Introduction Competitive algorithms were introduced by Sleator and Tarjan [ST] in the context of searching a linked list of elements and the paging problem. [ST] sought a worst case complexity measure for on-line algorithms that have to make decisions based upon current events without knowing what the future holds. The immediate problem is that on-line algorithms are incomparable, on-line algorithm A may be better than on-line algorithm B for one ... |
| File Format | |
| Publisher Date | 1990-01-01 |
| Access Restriction | Open |
| Subject Keyword | Arbitrary Metric Space Competitive K-server Algorithm General Metric Space On-line Algorithm Current Event Deterministic Competitive K-server Algorithm Introduction Competitive Algorithm Minimal Competitive Ratio Non-constructive Proof Immediate Problem Previous Result Competitive Ratio Deterministic 3-server Competitive Algorithm Paging Problem K-server Conjecture Mm Tarjan St Metric Space 3-server Randomized Competitive Algorithm Bkt Case Complexity Measure |
| Content Type | Text |
| Resource Type | Article |
