2026-08-17T16:46:02Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24584 2025-12-16T14:01:09Z ddc:004 open_access

Smoothed Analysis of Online Metric Problems Coester, Christian Umenberger, Jack Online Algorithms Competitive Analysis Smoothed Analysis k-server k-taxi Metrical Service Systems We study three classical online problems - k-server, k-taxi, and chasing size k sets - through a lens of smoothed analysis. Our setting allows request locations to be adversarial up to small perturbations, interpolating between worst-case and average-case models. Specifically, we show that if the metric space is contained in a ball in any normed space and requests are drawn from distributions whose density functions are upper bounded by 1/σ times the uniform density over the ball, then all three problems admit polylog(k/σ)-competitive algorithms. Our approach is simple: it reduces smoothed instances to fully adversarial instances on finite metrics and leverages existing algorithms in a black-box manner. We also provide a lower bound showing that no algorithm can achieve a competitive ratio sub-polylogarithmic in k/σ, matching our upper bounds up to the exponent of the polylogarithm. In contrast, the best known competitive ratios for these problems in the fully adversarial setting are 2k-1, ∞ and Θ(k²), respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Coester and Jack Umenberger 2025 Is Part Of LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2025.115 urn:nbn:de:0030-drops-245847 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.115 eng https://creativecommons.org/licenses/by/4.0/legalcode