2026-07-21T15:08:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26456 2026-07-01T07:16:11Z ddc:004 open_access

Chasing Small Sets Optimally Against Adaptive Adversaries Coester, Christian Tudose, Alexa online algorithms competitive analysis chasing small sets layered graph traversal metrical service systems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Coester and Alexa Tudose 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.67 urn:nbn:de:0030-drops-264568 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.67 eng https://creativecommons.org/licenses/by/4.0/legalcode