Chasing small sets optimally against adaptive adversaries

Conference item

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 Ω(2k )∩O(k2 k ) 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.

Authors: Coester, C; Tudose, A

• Publication status: Accepted
• Peer review status: Peer reviewed
• Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
• Acceptance date: 2026-04-20
• Event title: 53rd EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2026)
• Event location: Egham, UK
• Event website: https://icalppodcspaa2026.cs.rhul.ac.uk/icalp/
• Event start date: 2026-07-07
• Event end date: 2026-07-10
• Language: English
• Keywords: online algorithms; competitive analysis; chasing small sets; layered graph traversal; metrical service systems