# Smoothed Analysis of Online Metric Problems

arXiv: https://arxiv.org/abs/2507.17834 · HTML: https://mlsanity.com/paper/2507.17834/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Jul 2025.

## Built on by (most cited first, 1 of 1)

- [Smoothed Analysis of Inconsistent A*](https://mlsanity.com/paper/2609.23680/) (2026)

## Abstract (arXiv)

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 Theta(k2), respectively.