# Chasing Small Sets Optimally Against Adaptive Adversaries

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

## Key facts

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

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

- [Learning-Augmented Online Minimization with Dual Predictions](https://mlsanity.com/paper/2606.05380/) (2026)

## Abstract (arXiv)

We study deterministic online algorithms for the problem of chasing sets of cardinality at most k in a metric space, also known as metrical service systems and equivalent to width-k layered graph traversal. We resolve the 30-year-old gap of Omega(2k)cap O(k2k) on the competitive ratio of this problem by giving an O(2k)-competitive deterministic algorithm. This bound is optimal even among randomized algorithms against adaptive adversaries. We also (slightly) improve the deterministic lower bound to Dk, defined recursively by D1=1 and Dk+1=2Dk+√8+8Dk+3, which we conjecture to be exactly tight. For k=3, we provide a matching upper bound of D3. Our results imply slightly improved upper and lower bounds for distributed asynchronous collective tree exploration and for the k-taxi problem, respectively. Our algorithm generalizes the classical doubling strategy, previously known to be optimal for k=2. The previous best bound for general k was achieved by the generalized work function algorithm (WFA), and was known to be tight for WFA. Our improved bound therefore implies that WFA is sub-optimal for chasing small sets.