Smoothed Analysis of Online Metric Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913958552666112 |
|---|---|
| author | Coester, Christian Umenberger, Jack |
| author_facet | Coester, Christian Umenberger, Jack |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_17834 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Smoothed Analysis of Online Metric Problems Coester, Christian Umenberger, Jack Data Structures and Algorithms 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. |
| title | Smoothed Analysis of Online Metric Problems |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2507.17834 |