2 papers
cs.DS2015
An O(log k log^2 n)-competitive Randomized Algorithm for the k-Sever Problem
Wenbin Chen
In this paper, we show that there is an O(log k log^2 n)-competitive randomized algorithm for the k-sever problem on any metric space with n points, which improved the previous bes…
cs.DS2014
Settling the Randomized k-sever Conjecture on Some Special Metrics
Wenbin Chen
In this paper, we settle the randomized -sever conjecture for the following metric spaces: line, circle, Hierarchically well-separated tree (HST). Specially, we show that there…