Thumbnail
Access Restriction
Subscribed

Author Bansal, Nikhil ♦ Buchbinder, Niv ♦ Madry, Aleksander ♦ Naor, Joseph Seffi
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2015
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Competitive analysis ♦ K-server problem ♦ Randomization
Abstract We give the first polylogarithmic-competitive randomized online algorithm for the $\textit{k}-server$ problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of $Õ(log^{3}$ $\textit{n}$ $log^{2}$ $\textit{k})$ for any metric space on $\textit{n}$ points. Our algorithm improves upon the deterministic $(2\textit{k}-1)-competitive$ algorithm of Koutsoupias and Papadimitriou [Koutsoupias and Papadimitriou 1995] for a wide range of $\textit{n}.$
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2015-11-02
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 62
Issue Number 5
Page Count 49
Starting Page 1
Ending Page 49


Open content in new tab

   Open content in new tab
Source: ACM Digital Library