{"ID":2891484,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2507.17834","arxiv_id":"2507.17834","title":"Smoothed Analysis of Online Metric Problems","abstract":"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$, $\\infty$ and $Θ(k^2)$, respectively.","short_abstract":"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 i...","url_abs":"https://arxiv.org/abs/2507.17834","url_pdf":"https://arxiv.org/pdf/2507.17834v1","authors":"[\"Christian Coester\",\"Jack Umenberger\"]","published":"2025-07-23T18:01:13Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}