DocumentCode :
2722991
Title :
A Polylogarithmic-Competitive Algorithm for the k-Server Problem
Author :
Bansal, N. ; Buchbinder, N. ; Madry, A. ; Naor, J.
Author_Institution :
IBM T. J. Watson, NY, USA
fYear :
2011
fDate :
22-25 Oct. 2011
Firstpage :
267
Lastpage :
276
Abstract :
We give the first polylogarithmic-competitive randomized algorithm for the k-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of Õ(log3 n log2 k) for any metric space on n points. This improves upon the (2k-1)-competitive algorithm of Koutsoupias and Papadimitriou (J. ACM 1995) whenever n is sub-exponential in k.
Keywords :
queueing theory; randomised algorithms; (2k-1) competitive algorithm; arbitrary finite metric space; k-server problem; polylogarithmic competitive randomized algorithm; Algorithm design and analysis; Extraterrestrial measurements; Probability distribution; Resource management; Servers; Vectors; competitive analysis; k-server problem; randomized algorithms;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on
Conference_Location :
Palm Springs, CA
ISSN :
0272-5428
Print_ISBN :
978-1-4577-1843-4
Type :
conf
DOI :
10.1109/FOCS.2011.63
Filename :
6108181
Link To Document :
https://search.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2722991
بازگشت