# Metrical task systems on trees via mirror descent and unfair gluing

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Jul 2018.

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

- [Mixing predictions for online metric algorithms](https://mlsanity.com/paper/2304.01781/) (2023)
- [Algorithms for Caching and MTS with reduced number of predictions](https://mlsanity.com/paper/2404.06280/) (2024)
- [Online Conversion with Switching Costs: Robust and Learning-Augmented Algorithms](https://mlsanity.com/paper/2310.20598/) (2023)
- [Movement Penalized Bayesian Optimization with Application to Wind Energy Systems](https://mlsanity.com/paper/2210.08087/) (2022)
- [Chasing Convex Functions with Long-term Constraints](https://mlsanity.com/paper/2402.14012/) (2024)
- [Learning-Augmented Algorithms for MTS with Bandit Access to Multiple Predictors](https://mlsanity.com/paper/2506.05479/) (2025)
- [Online Covering with Multiple Experts](https://mlsanity.com/paper/2312.14564/) (2023)
- [Dynamic Data Layout Optimization with Worst-case Guarantees](https://mlsanity.com/paper/2405.04984/) (2024)
- [Learning-Augmented Competitive Algorithms for Spatiotemporal Online Allocation with Deadline Constraints](https://mlsanity.com/paper/2408.07831/) (2024)
- [Learning-Augmented Online Minimization with Dual Predictions](https://mlsanity.com/paper/2606.05380/) (2026)
- [Smoothed Online Combinatorial Optimization Using Imperfect Predictions](https://mlsanity.com/paper/2204.10979/) (2022)

## Abstract (arXiv)

We consider metrical task systems on tree metrics, and present an O(depth × log n)-competitive randomized algorithm based on the mirror descent framework introduced in our prior work on the k-server problem. For the special case of hierarchically separated trees (HSTs), we use mirror descent to refine the standard approach based on gluing unfair metrical task systems. This yields an O(log n)-competitive algorithm for HSTs, thus removing an extraneous loglog n in the bound of Fiat and Mendel (2003). Combined with well-known HST embedding theorems, this also gives an O((log n)2)-competitive randomized algorithm for every n-point metric space.