pith. machine review for the scientific record. sign in

arxiv: 2605.10927 · v1 · submitted 2026-05-11 · 💻 cs.DS

Recognition: no theorem link

Chasing Small Sets Optimally Against Adaptive Adversaries

Christian Coester , Alexa Tudose
Authors on Pith no claims yet

Pith reviewed 2026-05-12 03:39 UTC · model grok-4.3

classification 💻 cs.DS
keywords set chasingonline algorithmscompetitive analysismetric spacesadaptive adversariesdoubling strategymetrical service systemslayered graph traversal
0
0 comments X

The pith

A generalized doubling strategy yields an O(2^k)-competitive deterministic algorithm for chasing sets of size at most k in metric spaces.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper resolves a 30-year gap in competitive analysis for the k-set chasing problem by presenting a deterministic online algorithm that achieves an O(2^k) competitive ratio in any metric space. This bound is tight, matching the known Omega(2^k) lower bound and holding even against randomized algorithms when the adversary is adaptive. The method extends the classical doubling strategy previously optimal only for k=2, and it also refines the deterministic lower bound to a new recursive function D_k that is exactly matched for k=3. The results tighten known bounds for the k-taxi problem and distributed asynchronous collective tree exploration.

Core claim

We give an O(2^k)-competitive deterministic algorithm for chasing sets of cardinality at most k in arbitrary metric spaces against adaptive adversaries. This bound is optimal even among randomized algorithms. The algorithm generalizes the classical doubling strategy and is strictly better than the generalized work function algorithm.

What carries the argument

The generalized doubling strategy, which extends the k=2 doubling approach to maintain and double coverage over potential sets of size k while ensuring the O(2^k) bound holds in arbitrary metrics.

If this is right

  • The generalized work function algorithm is sub-optimal for chasing small sets.
  • Slightly improved upper bounds hold for distributed asynchronous collective tree exploration.
  • Slightly improved lower bounds hold for the k-taxi problem.
  • The new recursive lower bound D_k is matched exactly by the algorithm for k=3.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Doubling generalizations may close similar competitive gaps in other online problems on metric spaces or layered graphs.
  • The exact D_k values for small k could enable practical tuning of service systems or routing protocols where k is constant.
  • Robustness against adaptive adversaries suggests the bound applies directly to dynamic request models in distributed computing.

Load-bearing premise

The generalized doubling strategy admits an O(2^k) competitive analysis that holds for arbitrary metric spaces and against adaptive adversaries.

What would settle it

A concrete metric space and adaptive sequence of k-sets for which the algorithm's total movement cost exceeds C times 2^k times the optimal offline cost for arbitrarily large C.

Figures

Figures reproduced from arXiv: 2605.10927 by Alexa Tudose, Christian Coester.

Figure 1
Figure 1. Figure 1: Non-trivial stemmed tree S. Denoting by T the tree on which the evolving tree game is played, we define the depth of a node as the number of edges on the path connecting that node and the root of T, and define the depth of T as the maximum depth of one of its nodes. As in [BCR22], we parametrize the evolving tree game by depth instead of width in sections 4 and 5 concerned with our main algorithm. We say t… view at source ↗
Figure 2
Figure 2. Figure 2: Deletion examples. ALG represents the position of the algorithm and the labels next to [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Extreme tree T ′′. ALG represents the position of the algorithm and the labels next to the edges indicate weights. 5.1 Algorithm description We are now ready to describe our algorithm. Recall that the tree T 0 on which the game is played is initialized to a have a single leaf, connected to the root by a zero-length edge. We initialize the distorted tree T in the same manner. Since the depth k of the instan… view at source ↗
Figure 4
Figure 4. Figure 4: Stages of deletion. OPT denotes the location of the optimal leaf in the subtree and ALG [PITH_FULL_IMAGE:figures/full_fig_p018_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: A tree T with three leaves {l1, l2, l3}. The edges are labelled by their weights. 22 [PITH_FULL_IMAGE:figures/full_fig_p023_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Deletion cases. ALG represents the position of the algorithm and the labels next to the [PITH_FULL_IMAGE:figures/full_fig_p025_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Deletion example for width k = 4. ALG represents the position of the algorithm and the labels next to the edges indicate weights. C Proof that Dk = O(2k ) Claim 23. For k ≥ 2, it holds that Dk ≤ 2 k+4 − √ 2 k+9. Proof. By induction. The base case k = 2 holds because D2 = 9 < 2 6 − √ 2 11. For the inductive step, we plug in the formula for Dk+1 and use the inductive hypothesis to obtain Dk+1 = 2Dk + p 8(1 +… view at source ↗
Figure 8
Figure 8. Figure 8: Lower bound against adaptive online adversaries. [PITH_FULL_IMAGE:figures/full_fig_p031_8.png] view at source ↗
read the original 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 $\Omega(2^k)\cap 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=1$ and $D_{k+1}=2D_k+\sqrt{8+8D_k}+3$, which we conjecture to be exactly tight. For $k=3$, we provide a matching upper bound of $D_3$. 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript presents a deterministic online algorithm for chasing sets of cardinality at most k in arbitrary metric spaces (equivalent to width-k layered graph traversal). It claims an O(2^k)-competitive ratio against adaptive adversaries by generalizing the classical doubling strategy via recursive doubling phases and a potential-function charging argument; this closes the 30-year gap between the known Ω(2^k) lower bound and the prior O(k 2^k) upper bound from the generalized work-function algorithm. The paper also gives a new deterministic lower bound D_k (defined recursively) that is conjectured to be tight, proves a matching upper bound of D_3 for k=3, and notes improved bounds for distributed asynchronous collective tree exploration and the k-taxi problem.

Significance. If the analysis is correct, the result is a significant contribution to online algorithms: it resolves an open question on the competitive ratio of metrical service systems, demonstrates that the generalized WFA is suboptimal for this problem, and establishes optimality even against randomized algorithms and adaptive adversaries. The explicit potential-function argument that charges movement cost to the offline optimum while bounding phase transitions by O(2^k) in arbitrary metrics is a strength, as is the handling of adaptivity without hidden restrictions on the metric.

minor comments (3)
  1. [Abstract] Abstract: the statement that the new lower bound D_k is only a 'slight' improvement should be quantified by recalling the previous best lower bound and the precise asymptotic growth of D_k.
  2. [§3] The recursive definition of the algorithm (likely §3) would benefit from explicit pseudocode or a clear inductive description of how the doubling phases are instantiated for general k, including the base case and the rule for selecting the next phase center after an adversary move.
  3. [§4] The potential-function analysis (likely §4) should include a short remark confirming that the charging scheme remains valid when the adversary chooses the next k-set adaptively after observing the algorithm's position; while the text asserts this, a one-sentence pointer to the relevant induction step would help.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and insightful review of our manuscript. We are pleased that the referee acknowledges the significance of our results in closing the long-standing gap for the competitive ratio of chasing k-sets against adaptive adversaries. As no specific major comments were provided in the report, we have no points to address individually. We will make any necessary minor revisions as directed by the editor.

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper's central result is an explicit O(2^k)-competitive deterministic algorithm obtained by generalizing the classical doubling strategy, together with a self-contained potential-function analysis that charges movement costs to the offline optimum and bounds phase transitions by O(2^k). This analysis is stated to hold in arbitrary metric spaces against adaptive adversaries and does not rely on fitted parameters, self-citations, or reductions to prior results by the same authors. The improved lower bound D_k is defined recursively from first principles and is matched only for the special case k=3; neither step reduces by construction to the algorithm's inputs. The derivation is therefore independent and self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard metric properties and the definition of competitive ratio against adaptive adversaries; no free parameters, invented entities, or ad-hoc axioms are introduced.

axioms (2)
  • domain assumption Inputs are sequences of sets of size at most k in an arbitrary metric space.
    Core definition of the chasing problem.
  • domain assumption Competitive ratio is measured against an adaptive adversary.
    Standard model for the optimality claim.

pith-pipeline@v0.9.0 · 5528 in / 1233 out tokens · 68474 ms · 2026-05-12T03:39:53.430365+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Larmore , title =

    Marek Chrobak and Lawrence L. Larmore , title =. On-Line Algorithms, Proceedings of a. 1991 , url =

    work page 1991

  2. [2]

    Ramesh , title =

    H. Ramesh , title =. J. Algorithms , volume =. 1995 , url =

    work page 1995

  3. [3]

    ACM Transactions on Algorithms , volume=

    Online metric algorithms with untrusted predictions , author=. ACM Transactions on Algorithms , volume=

    work page

  4. [4]

    Shortest Paths without a Map, but with an Entropic Regularizer , booktitle =

    S. Shortest Paths without a Map, but with an Entropic Regularizer , booktitle =. 2022 , url =

    work page 2022

  5. [5]

    1991 , issn =

    Shortest paths without a map , journal =. 1991 , issn =. doi:https://doi.org/10.1016/0304-3975(91)90263-2 , url =

    work page doi:10.1016/0304-3975(91)90263-2 1991

  6. [6]

    1993 , issn =

    Searching in the Plane , journal =. 1993 , issn =. doi:https://doi.org/10.1006/inco.1993.1054 , url =

    work page doi:10.1006/inco.1993.1054 1993

  7. [7]

    Asynchronous Collective Tree Exploration: a Distributed Algorithm, and a new Lower Bound , journal=

    Romain Cosson and Laurent Massouli. Asynchronous Collective Tree Exploration: a Distributed Algorithm, and a new Lower Bound , journal=

    work page

  8. [8]

    , title =

    Borodin, Allan and Linial, Nathan and Saks, Michael E. , title =. 1992 , issue_date =. doi:10.1145/146585.146588 , journal =

    work page doi:10.1145/146585.146588 1992

  9. [9]

    Foster and Howard J

    Amos Fiat and Dean P. Foster and Howard J. Karloff and Yuval Rabani and Yiftach Ravid and Sundar Vishwanathan , title =. 1998 , url =. doi:10.1137/S0097539795279943 , timestamp =

    work page doi:10.1137/s0097539795279943 1998

  10. [10]

    Burley , title =

    William R. Burley , title =. J. Algorithms , volume =. 1996 , url =. doi:10.1006/JAGM.1996.0024 , timestamp =

    work page doi:10.1006/jagm.1996.0024 1996

  11. [11]

    Papadimitriou , title =

    Elias Koutsoupias and Christos H. Papadimitriou , title =. J. 1995 , url =

    work page 1995

  12. [12]

    Proceedings of the 51st Annual

    Christian Coester and Elias Koutsoupias , title =. Proceedings of the 51st Annual. 2019 , url =

    work page 2019

  13. [13]

    Mixing Predictions for Online Metric Algorithms , booktitle =

    Antonios Antoniadis and Christian Coester and Marek Eli. Mixing Predictions for Online Metric Algorithms , booktitle =. 2023 , url =

    work page 2023

  14. [14]

    The Randomized k-Server Conjecture Is False! , booktitle =

    S. The Randomized k-Server Conjecture Is False! , booktitle =. 2023 , url =

    work page 2023

  15. [15]

    A Regression Approach to Learning-Augmented Online Algorithms , url =

    Anand, Keerti and Ge, Rong and Kumar, Amit and Panigrahi, Debmalya , booktitle =. A Regression Approach to Learning-Augmented Online Algorithms , url =

    work page

  16. [16]

    On the Power of Randomization in On-Line Algorithms , journal =

    Shai Ben. On the Power of Randomization in On-Line Algorithms , journal =

    work page

  17. [17]

    and Linial, N

    Friedman, J. and Linial, N. , journal =. On Convex Body Chasing. , url =

    work page

  18. [18]

    Competitively Chasing Convex Bodies , journal =

    S. Competitively Chasing Convex Bodies , journal =. 2023 , url =

    work page 2023

  19. [19]

    C. J. Argue and Anupam Gupta and Ziye Tang and Guru Guruganesh , title =. J. 2021 , url =

    work page 2021

  20. [20]

    Proceedings of the 2020

    Mark Sellke , title =. Proceedings of the 2020. 2020 , url =

    work page 2020

  21. [21]

    Ricardo A. Baeza. Searching in the Plane , journal =. 1993 , url =

    work page 1993

  22. [22]

    Beck, Anatole and Newman, D. J. , doi =. Yet more on the linear search problem , url =. Israel Journal of Mathematics , number =

    work page

  23. [23]

    Proceedings of the 2025 Annual

    Xingjian Bai and Christian Coester and Romain Cosson , title =. Proceedings of the 2025 Annual. 2025 , url =

    work page 2025

  24. [24]

    Online 3-Taxi on General Metrics , booktitle =

    Christian Coester and Tze. Online 3-Taxi on General Metrics , booktitle =. 2026 , url =

    work page 2026