论文标题
统一指标上的广义$ k $ - 服务器问题的无内存算法
Memoryless Algorithms for the Generalized $k$-server Problem on Uniform Metrics
论文作者
论文摘要
我们考虑统一指标上的广义$ k $ - 服务器问题。我们研究无内存算法的功能，并在其竞争比率上显示出$θ（k！）$的紧密界限。特别是我们表明\ textIt {谐波算法}达到了这个竞争比率并提供匹配的下限。这改善了$ \ \ \ 2^{2^k} $ chiplunkar和Vishwanathan的双重指数界限，用于具有不同权重的均匀度量标准的更通用的设置。
We consider the generalized $k$-server problem on uniform metrics. We study the power of memoryless algorithms and show tight bounds of $Θ(k!)$ on their competitive ratio. In particular we show that the \textit{Harmonic Algorithm} achieves this competitive ratio and provide matching lower bounds. This improves the $\approx 2^{2^k}$ doubly-exponential bound of Chiplunkar and Vishwanathan for the more general setting of uniform metrics with different weights.
