The Randomized ?-Server Conjecture Is False!
The Randomized ?-Server Conjecture Is False!
复制标题
随机?服务器猜想是错误的！
DOI：
--
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Y. Rabani
中科院分区：
文献类型：
--
作者：
Sébastien Bubeck;Christian Coester;Y. Rabani
我们证明了几个新的下界的随机竞争比的k-服务器问题和其他相关问题，解决了一些长期存在的问题。特别是，测量任务系统（MTS），我们不对称解决的竞争比，并获得了第一次改进的存在下限，因为该模型35年前（1987年）推出。更具体地说，我们证明了：（1）存在（k+1）-点度量空间，其中k-服务台问题的随机竞争比为Ω（log 2k）.这反驳了民间传说中的猜想（已知在某些度量族中成立），即在所有至少有k+1个点的度量空间中，竞争比是Θ（logk）。(2)因此，存在n点度量空间，其中MTS的随机竞争比为Ω（log 2 n）。这与适用于所有指标的上限相匹配。以前最好的存在下界是Ω（logn）（已知它对某些度量族是紧的）。(3)对所有k<n∈，对所有n点度量空间，随机k-服务器竞争比至少为Ω（logk），因此随机MTS竞争比至少为Ω（logn）.这些普遍下界是渐近紧的。之前的界限分别是Ω（logk/loglogk）和Ω（logn/loglogn）。(4)w-集度量服务系统问题及其等价的宽度-w分层图遍历问题的随机竞争比为Ω（w ~ 2）。这稍微改进了以前的下界，并与最近发现的上界相匹配。(5)我们的研究结果意味着其他问题，如k-出租车，分布式寻呼和度量分配的改进下界。这些下界共享一个共同的线索，并且除了第三个界限之外，也共享一个共同的构造。
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 Ω(log2 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 Θ(logk). (2) Consequently, there exist n-point metric spaces in which the randomized competitive ratio for MTS is Ω(log2 n). This matches the upper bound that holds for all metrics. The previously best existential lower bound was Ω(logn) (which was known to be tight for some families of metrics). (3) For all k<n∈, for all n-point metric spaces the randomized k-server competitive ratio is at least Ω(logk), and consequently the randomized MTS competitive ratio is at least Ω(logn). These universal lower bounds are asymptotically tight. The previous bounds were Ω(logk/loglogk) and Ω(logn/loglogn), respectively. (4) The randomized competitive ratio for the w-set metrical service systems problem, and its equivalent width-w layered graph traversal problem, is Ω(w2). 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.
影响因子：
1
作者：
Coester, Christian;Lee, James R.
通讯作者：
Lee, James R.