We show that a potential-based algorithm for the fractional $k$-serverproblem on hierarchically separated trees (HSTs) with competitive ratio $f(k)$can be used to obtain a randomized algorithm for any metric space withcompetitive ratio $f(k)^2 O((log k)^2)$. Employing the $O((logk)^2)$-competitive algorithm for HSTs from our joint work with Bubeck, Cohen,Lee, and Mk{a}dry (2017), this yields an $O((log k)^6)$-competitive algorithmfor the $k$-server problem on general metric spaces. The best previous result independent of the geometry of the underlying metricspace is the $2k-1$ competitive ratio established for the deterministic workfunction algorithm by Koutsoupias and Papadimitriou (1995). Even for thespecial case when the underlying metric space is the real line, the best knowncompetitive ratio was $k$. Since deterministic algorithms can do no better than$k$ on any metric space with at least $k+1$ points, this establishes that forevery metric space on which the problem is non-trivial, randomized algorithmsgive an exponential improvement over deterministic algorithms.
展开▼
机译：我们表明，具有竞争比率F（k）$的分层分离的树（HSTS）上的基于分数K $ -ServerProblem的潜在算法可用于获得随机竞争比率$ f（k的任何公制空间的随机算法）^ 2 o（（ log k）^ 2）$。使用$ O（（ logk）^ 2）$ - 从我们的联合工作与冒泡，科恩，李和m {a} dry（2017）中的HSTS竞争算法，这会产生$ o（（ log k）^ 6）$竞争性算法在常规度量空间上的$ k $ -server问题。独立于底层元质空间的几何形状的最佳结果是Koutsoupias和Papadimitriou（1995）为确定性工作功能算法建立的2K-1 $竞争比率。即使对于底层公制空间是实际线路时，即使是当实际线路时，也是最好的已知比例为$ k $。由于确定性算法可以在任何具有至少$ k + 1 $积分的公制空间上没有比$ k $更好，这建立了问题是非琐碎的，随机算法的永远的公制空间对确定性算法的指数改进。
展开▼
