2022/11/10 by Sébastien Bubeck, Christian Coester, Bubeck, Sébastien +3 · 3 citations
Computer Science · Engineering · #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Metric Geometry (math.MG) #Optimization and Search Problems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2211.05753
openalex publication_date 2022/11/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Θ(log k). 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 Ω(log n) (which was known to be tight for some families of metrics). 3. For all k