期刊
JOURNAL OF THE ACM
卷 62, 期 5, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2783434
关键词
Design; Algorithms; k-server problem; competitive analysis; randomization
类别
资金
- NWO Vidi grant [639.022.211]
- ERC [617951]
- ISF [954/11]
- BSF [2010426]
- NSF [CCF-0829878]
- ONR [N00014-11-1-0053]
We give the first polylogarithmic-competitive randomized online algorithm for the k-server problem on an arbitrary finite metric space. In particular, our algorithm achieves a competitive ratio of (O) over tilde (log(3) n log(2) k) for any metric space on n points. Our algorithm improves upon the deterministic (2k - 1)-competitive algorithm of Koutsoupias and Papadimitriou [Koutsoupias and Papadimitriou 1995] for a wide range of n.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据