2026-07-20T10:41:56Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24940 2026-02-09T08:02:20Z ddc:004 open_access

Time-Optimal k-Server Frei, Fabian Komm, Dennis Stocker, Moritz Whittington, Philip k-server problem optimizing time instead of distance deterministic and randomized algorithms Yao’s principle The time-optimal k-server problem minimizes the time spent instead of the distance traveled when serving n requests, appearing one after the other, with k servers in a metric space. The classical distance model was motivated by a hard disk with k heads. Instead of minimal head movements, the time model aims for optimal reading speeds. This paper provides a lower bound of 2k-1 on the competitive ratio of any deterministic online algorithm for the time-optimal k-server problem on a specifically designed metric space. This lower bound coincides with the best known upper bound on the competitive ratio for the classical k-server problem, achieved by the famous work function algorithm. We provide further lower bounds of k+1 for all Euclidean spaces and k for uniform metric spaces. Our most technical result, proven by applying Yao’s principle to a suitable instance distribution, is a lower bound of k+H_k-1 that holds even for randomized algorithms, which contrasts with the best known lower bound for the classical problem, which is polylogarithmic in k. We hope to initiate further intensive study of this natural problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fabian Frei and Dennis Komm and Moritz Stocker and Philip Whittington 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.32 urn:nbn:de:0030-drops-249407 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.32 eng https://creativecommons.org/licenses/by/4.0/legalcode