论文标题
随机$ k $ - 服务器的猜想是错误的！
The Randomized $k$-Server Conjecture is False!
论文作者
论文摘要
我们证明，对于$ k $ - 服务器问题和其他相关问题的随机竞争比率，我们证明了一些新的下限，从而解决了一些长期的猜想。特别是，对于度量任务系统（MTS），我们不可分割地解决竞争比率，并获得自35年前（1987年）引入模型以来的生存下限的首次改进。 更具体地说，我们表明： 1。存在$（k+1）$ - 点公制空间，其中$ k $ - 服务器问题的随机竞争比为$ω（\ log^2 k）$。这驳斥了民间传说的猜想（已知在某些指标家庭中持有），在所有指标空间中至少具有$ k+1 $ $的积分中，竞争比为$θ（\ log log k）$。 2。因此，存在$ n $ - 点公制空间，其中MTS的随机竞争比为$ω（\ log^2 n）$。这匹配所有指标的上限。以前最好的存在下限是$ω（\ log n）$（对于某些指标家庭而言，这很紧）。 3。对于所有$ k <n \ in \ mathbb n $，对于 * all * $ n $ - 点公式空间，随机$ k $ - server竞争比至少为$ω（\ log k）$，因此随机MTS竞争比至少为$ $ω（\ log log n）$。这些通用的下限渐近地很紧。先前的界限分别为$ω（\ log k/\ log \ log k）$和$ω（\ log n/\ log \ log n）$。 4。$ W $集的度量服务系统问题的随机竞争比及其等效宽度 - $ W $分层遍历问题，为$ω（W^2）$。这稍微改善了以前的下限，并与最近发现的上限匹配。 5。我们的结果暗示了其他问题的下限，例如$ k $ - taxi，分布式分页和度量分配。 这些下限共享一个共同的线，除第三界外，也共有一个共同的结构。
We prove a few new lower bounds on the randomized competitive ratio for the $k$-server problem and other related problems, resolving some long-standing conjectures. In particular, for metrical task systems (MTS) we asympotically settle the competitive ratio and obtain the first improvement to an existential lower bound since the introduction of the model 35 years ago (in 1987). More concretely, we show: 1. There exist $(k+1)$-point metric spaces in which the randomized competitive ratio for the $k$-server problem is $Ω(\log^2 k)$. This refutes the folklore conjecture (which is known to hold in some families of metrics) that in all metric spaces with at least $k+1$ points, the competitive ratio is $Θ(\log k)$. 2. Consequently, there exist $n$-point metric spaces in which the randomized competitive ratio for MTS is $Ω(\log^2 n)$. This matches the upper bound that holds for all metrics. The previously best existential lower bound was $Ω(\log n)$ (which was known to be tight for some families of metrics). 3. For all $k<n\in\mathbb N$, for *all* $n$-point metric spaces the randomized $k$-server competitive ratio is at least $Ω(\log k)$, and consequently the randomized MTS competitive ratio is at least $Ω(\log n)$. These universal lower bounds are asymptotically tight. The previous bounds were $Ω(\log k/\log\log k)$ and $Ω(\log n/\log \log n)$, respectively. 4. The randomized competitive ratio for the $w$-set metrical service systems problem, and its equivalent width-$w$ layered graph traversal problem, is $Ω(w^2)$. This slightly improves the previous lower bound and matches the recently discovered upper bound. 5. Our results imply improved lower bounds for other problems like $k$-taxi, distributed paging and metric allocation. These lower bounds share a common thread, and other than the third bound, also a common construction.
