Premium
A randomized on–line algorithm for the k –server problem on a line
Author(s) -
Csaba Béla,
Lodha Sachin
Publication year - 2006
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20124
Subject(s) - big data , metric space , line (geometry) , randomized algorithm , paging , competitive analysis , computer science , real line , combinatorics , metric (unit) , online algorithm , algorithm , space (punctuation) , mathematics , discrete mathematics , upper and lower bounds , operating system , mathematical analysis , operations management , geometry , economics
The k – server problem is one of the most important and well‐studied problems in the area of on–line computation. Its importance stems from the fact that it models many practical problems like multi‐level memory paging encountered in operating systems, weighted caching used in the management of web caches, head motion planning of multi‐headed disks, and robot motion planning. In this paper, we investigate its randomized version for which Θ(log k )–competitiveness is conjectured and yet hardly any < k competitive algorithms are known, even for the simplest of metric spaces of O ( k ) size. We present a $O(n^{2/3}\log{n})$ –competitive randomized k –server algorithm against an oblivious adversary when the underlying metric space is given by n equally spaced points on a line $({\cal L}(n))$ . This algorithm is < k competitive for $n = k + o\big(\big({k \over \log k}\big)^{3/2}\big)$ . Thus, it provides a super–linear bound for n with o ( k )–competitiveness for the first time and improves the best results known so far for the range $n-k \in \big[o(k), o\big(\big({k \over \log k}\big)^{3/2}\big)\big]$ on ${\cal L}(n)$ . © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006