Proceedings of the 55th Annual ACM Symposium on Theory of Computing
Proceedings of the 55th Annual ACM Symposium on Theory of Computing
复制标题
DOI：
10.1145/3564246
复制
发表时间：
2011-06
期刊：
影响因子：
--
通讯作者：
L. Fortnow;S. Vadhan
中科院分区：
文献类型：
--
作者：
L. Fortnow;S. Vadhan
我们证明了k-服务器问题和其他相关问题的随机竞争比的几个新的下界，解决了一些长期存在的问题。特别地，对于度量任务系统（MTS），我们对竞争比进行了非对称的求解，得到了自该模型35年前（1987年）提出以来的第一个改进，更具体地，我们证明了：（1）存在（k+1）-点度量空间，其中k-服务器问题的随机竞争比为Ω（log 2k）.这反驳了民间传说中的猜想（已知在某些度量族中成立），即在所有至少有k +1个点的度量空间中，竞争比是Θ（logk）。(2)因此，存在n点度量空间，其中MTS的随机竞争比为Ω（log 2n）.这与适用于所有指标的上限相匹配。以前最好的存在下界是Ω（logn）（已知它对某些度量族是紧的）。(3)对所有k <n∈，对所有n点度量空间，随机化k-服务台竞争比至少为Ω（logk），从而随机化MTS竞争比至少为Ω（logn）.这些普遍下界是渐近紧的。之前的界限分别是Ω（logk/loglogk）和Ω（logn/loglogn）。(4)w-集度量服务系统问题及其等价的宽度-分层图遍历问题的随机竞争比为Ω（w ~ 2）。这稍微改进了以前的下界，并与最近发现的上界相匹配。(5)我们的结果意味着改进的下界为其他问题，如出租车，分布式分页，和度量分配。这些下界共享一个共同的线程，和其他的第三界，也是一个共同的建设。
We prove a few new lower bounds on the randomized competitive ratio for thek-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 thek-server problem is Ω(log2k). This refutes the folklore conjecture (which is known to hold in some families of metrics) that in all metric spaces with at leastk+1 points, the competitive ratio is Θ(logk). (2) Consequently, there existn-point metric spaces in which the randomized competitive ratio for MTS is Ω(log2n). 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 allk<n∈, foralln-point metric spaces the randomizedk-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 thew-set metrical service systems problem, and its equivalent width-wlayered 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 likek-taxi, distributed paging, and metric allocation.These lower bounds share a common thread, and other than the third bound, also a common construction.