2026-07-23T22:38:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22195 2024-12-05T15:18:03Z ddc:004 open_access

A Decomposition Approach to the Weighted k-Server Problem Ayyadevara, Nikhil Chiplunkar, Ashish Sharma, Amatya Online Algorithms k-server paging A natural variant of the classical online k-server problem is the weighted k-server problem, where the cost of moving a server is its weight times the distance through which it moves. Despite its apparent simplicity, the weighted k-server problem is extremely poorly understood. Specifically, even on uniform metric spaces, finding the optimum competitive ratio of randomized algorithms remains an open problem - the best upper bound known is 2^{2^{k+O(1)}} due to a deterministic algorithm (Bansal et al., 2018), and the best lower bound known is Ω(2^k) (Ayyadevara and Chiplunkar, 2021). With the aim of closing this exponential gap between the upper and lower bounds, we propose a decomposition approach for designing a randomized algorithm for weighted k-server on uniform metrics. Our first contribution includes two relaxed versions of the problem and a technique to obtain an algorithm for weighted k-server from algorithms for the two relaxed versions. Specifically, we prove that if there exists an α₁-competitive algorithm for one version (which we call Weighted k-Server - Service Pattern Construction) and there exists an α₂-competitive algorithm for the other version (which we call Weighted k-server - Revealed Service Pattern), then there exists an (α₁α₂)-competitive algorithm for weighted k-server on uniform metric spaces. Our second contribution is a 2^O(k²)-competitive randomized algorithm for Weighted k-server - Revealed Service Pattern. As a consequence, the task of designing a 2^poly(k)-competitive randomized algorithm for weighted k-server on uniform metrics reduces to designing a 2^poly(k)-competitive randomized algorithm for Weighted k-Server - Service Pattern Construction. Finally, we also prove that the Ω(2^k) lower bound for weighted k-server, in fact, holds for Weighted k-server - Revealed Service Pattern. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nikhil Ayyadevara and Ashish Chiplunkar and Amatya Sharma 2024 Is Part Of LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2024.6 urn:nbn:de:0030-drops-221954 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.6 eng https://creativecommons.org/licenses/by/4.0/legalcode