A General Decomposition Theorem for the k-Server Problem |
| |
Authors: | Steven S Seiden |
| |
Affiliation: | Department of Computer Science, Louisiana State University, 298 Coates Hall, Baton Rouge, Louisiana, 70803, f1 |
| |
Abstract: | The first general decomposition theorem for the k-server problem is presented. Whereas all previous theorems are for the case of a finite metric with k+1 points, the theorem given here allows an arbitrary number of points in the underlying metric space. This theorem implies O(polylog(k))-competitive randomized algorithms for certain metric spaces consisting of a polylogarithmic number of widely separated subspaces and takes a first step toward a general O(polylog(k))-competitive algorithm. The only other cases for which polylogarithmic competitive randomized algorithms are known are the uniform metric space and the weighted cache metric space with two weights. |
| |
Keywords: | Abbreviations: analysis of algorithmsAbbreviations: online algorithmsAbbreviations: k-server problem |
本文献已被 ScienceDirect 等数据库收录! |
|