The randomized k-server conjecture

ABSTRACT: 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 approximately O(\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 whenever n is sub-exponential in k.




BIO: 
Niv Buchbinder is a faculty member at the Open University, Israel. Previously he was a post-doctoral researcher at Microsoft Research, New England at Cambridge, MA.
His main research interests are algorithms for combinatorial problems in offline and online settings. He is also interested in algorithmic game theory problems.