DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.67

Chasing Small Sets Optimally Against Adaptive Adversaries

Authors: Christian Coester and Alexa Tudose

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

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 Ω(2^k)∩ O(k2^k) on the competitive ratio of this problem by giving an O(2^k)-competitive deterministic algorithm. This bound is optimal even among randomized algorithms against adaptive adversaries. We also (slightly) improve the deterministic lower bound to D_k, defined recursively by D₁ = 1 and D_{k+1} = 2D_k+√{8+8D_k}+3, which we conjecture to be exactly tight. For k = 3, we provide a matching upper bound of D₃. 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.

Cite as

Christian Coester and Alexa Tudose. Chasing Small Sets Optimally Against Adaptive Adversaries. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 67:1-67:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{coester_et_al:LIPIcs.ICALP.2026.67,
  author =	{Coester, Christian and Tudose, Alexa},
  title =	{{Chasing Small Sets Optimally Against Adaptive Adversaries}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{67:1--67:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.67},
  URN =		{urn:nbn:de:0030-drops-264568},
  doi =		{10.4230/LIPIcs.ICALP.2026.67},
  annote =	{Keywords: online algorithms, competitive analysis, chasing small sets, layered graph traversal, metrical service systems}
}

Search Results

Documents authored by Tudose, Alexa

Chasing Small Sets Optimally Against Adaptive Adversaries

Abstract

Cite as

Thanks for your feedback!

Could not send message