# k-server via multiscale entropic regularization

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Nov 2017.

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

- [Parsimonious Learning-Augmented Caching](https://mlsanity.com/paper/2202.04262/) (2022)
- [No-Regret Caching via Online Mirror Descent](https://mlsanity.com/paper/2101.12588/) (2021)
- [Double Coverage with Machine-Learned Advice](https://mlsanity.com/paper/2103.01640/) (2021)
- [Fast Tree-Field Integrators: From Low Displacement Rank to Topological Transformers](https://mlsanity.com/paper/2406.15881/) (2024)
- [Online Covering with Multiple Experts](https://mlsanity.com/paper/2312.14564/) (2023)
- [Convergence Analysis of Stochastic Saddle Point Mirror Descent Algorithm -- A Projected Dynamical View Point](https://mlsanity.com/paper/2404.04907/) (2024)
- [Online Algorithms via Minimax and Posterior Matching](https://mlsanity.com/paper/2608.01616/) (2026)

## Abstract (arXiv)

We present an O((log k)2)-competitive randomized algorithm for the k-server problem on hierarchically separated trees (HSTs). This is the first o(k)-competitive randomized algorithm for which the competitive ratio is independent of the size of the underlying HST. Our algorithm is designed in the framework of online mirror descent where the mirror map is a multiscale entropy. When combined with Bartal's static HST embedding reduction, this leads to an O((log k)2 log n)-competitive algorithm on any n-point metric space. We give a new dynamic HST embedding that yields an O((log k)3 log Delta)-competitive algorithm on any metric space where the ratio of the largest to smallest non-zero distance is at most Delta.