Chasing Small Sets Optimally Against Adaptive Adversaries

Our main result is the following.

Our upper bound matches the asymptotic lower bound of $\mathrm{\Omega }(2^k)$, and thus settles the optimal asymptotic competitive ratio of small set chasing (and, equivalently, layered graph traversal). In fact, we show in the full version of our paper [17, Appendix E] that our algorithm is asymptotically optimal not only among deterministic algorithms, but also among randomized algorithms competing against adaptive adversaries.

We additionally improve the exact lower bound for deterministic algorithms from $2^{k-2}$ [19] to $D_k$, defined recursively by

Note that $D_2=9$ is known to be the optimal competitive ratio for $k=2$. We conjecture that $D_k$ is exactly tight for all $k\ge 1$. We prove in the full version of our paper [17, Appendix A] that this indeed holds for $k=3$.

Since distributed asynchronous collective tree exploration reduces to width-$k$ layered graph traversal [18], and width-$k$ layered graph traversal reduces to $k$-taxi [15], we also obtain improved upper and lower bounds, respectively, for these problems.

Since competitive $k$-taxi algorithms for general (infinite) metric spaces are unknown except for $k\le 3$ [16], the constant-factor improvement is admittedly modest. Still, we hope it may offer insight for future algorithm design, especially since $D_2=9$ is known to be tight for the $2$-taxi problem [15]. In a similar vein, our algorithm for small set chasing is directly inspired by our lower bound construction.

Layered graph traversal is known to be equivalent to the case where the graph is a tree [19]. To simplify the description and analysis of our algorithms, it is convenient to further reduce the problem to a two-player game on a tree which evolves over time, as already done in [10]. This reduction is very natural: after layer $L_i$ is revealed, the algorithm only needs to remember the Steiner tree which connects the starting vertex $s$ to the vertices in $L_i$ (all vertices which are not part of this Steiner tree are “dead-ends”, since they do not have any descendant in $L_i$). Moreover, moving to a vertex in $L_i$ is equivalent to moving to a leaf of the Steiner tree. Therefore, we can model layered graph traversal as “chasing” the leaves of the Steiner tree, where the Steiner tree changes when a new layer is revealed. The game formulation helps express the changes of the Steiner tree as a sequence of simple transformations, which we can reason about more easily.

In Section 2, we first provide a sketch of our lower bound of $D_k$ for deterministic algorithms, which will serve to motivate our algorithm. As in the $2^{k-2}$ lower bound of [19], we use a recursive construction consisting of two branches, each containing a concatenation of lower bound instances of width $k-1$. In each step, the branch currently occupied by the algorithm is extended with an additional lower bound instance, while the other branch advances with zero-length edges. Unlike the construction of [19], which could be stopped at any time to yield a ratio of $2^{k-2}$, our improved lower bound is only attained at certain times when the ratio between the branch lengths is maximized over the course of the algorithm, and the bound we obtain depends on this ratio. Since we can stop an instance only at those specific moments, the adversary cannot easily control the absolute cost of an instance, as it depends on the behavior of the algorithm. Establishing a rigorous lower bound therefore requires some care: On the one hand, the cost of a recursive instance should not be too large, as otherwise an online algorithm could avoid it by switching to the other branch. On the other hand, it also should not be too small (e.g., exponentially decaying), as we need to be able to stack many recursive instances to obtain unbounded total cost. In the full version of our paper [17, Appendix D], we show that we can lower and upper bound the cost of an instance, which allows to use them effectively in the recursive construction.

Our lower bound suggests that there is a “sweet spot” for the ratio between the two branch lengths at which point the algorithm should switch to the other branch. Specifically, for instances of width $k$, the algorithm should switch to the other branch if the optimal value in its own branch is a factor $x_k:=1+\sqrt{\frac{2}{1+D_{k-1}}}$ larger than the optimal value in the other branch. This immediately suggests a simple online algorithm: switch to the shorter branch when the sweet spot of ratio $x_k$ between branch lengths is reached, and employ an analogous strategy (for smaller $k$) recursively within each branch. In the full version of our paper [17, Appendix A], we show that this strategy is indeed $D_3$-competitive for instances of width $3$.

However, generalizing the potential used for width $3$ to larger $k$ does not seem straightforward [17, Appendix B]. In Section 4, we derive a natural potential function inspired by the lower bound and show that it can almost prove $D_k$-competitiveness, except for two types of problems triggered by dead-ends in layered graph traversal. We then address these issues in Section 5 by refining the algorithm and potential function through two methods, which we call forgetting and imbalancing. While the presentation of these techniques will be specific to layered graph traversal, the underlying principles may be applicable more broadly. The motivating idea is to transform an instance into a canonical hard form, as witnessed in the lower bound construction. Forgetting corresponds to treating parts of the instance as if they had not yet been revealed, which we execute by truncating terms in the potential function. Imbalancing is a method of rounding an instance towards the highly unbalanced structure of worst-case instances, by distorting some edge lengths. Mathematically, the benefit of such distortions manifests through larger potential function values, and only costs a constant factor in the competitive ratio.

We now describe the evolving tree game, which is essentially the same as the one defined in [10] except that our growth operation is discrete rather than continuous and we define the game directly for binary trees.

We say that a tree is a stemmed binary tree if it satisfies the following conditions: a) it is a rooted tree, and the root has degree $1$; b) all vertices except the root have either $0$ or $2$ children.

The evolving tree game is a two-player game involving stemmed binary tree $T$ with nonnegative edge weights. We denote by $w_e$ the weight of an edge $e$. For a non-root node $u$, we denote by $e(u)$ the edge between $u$ and its parent. Initially, the tree consists of two vertices connected by a zero-length edge. The first player, called the adversary, can apply the following operations on $T$:

• $\mathrm{■}$

  Growth: for a leaf $l$ and $h>0$, increase the length of the edge $e(l)$ incident to $l$ by $h$.

• $\mathrm{■}$

  Deletion: for a leaf $l$ that is not the unique child of the root, delete $l$ together with its incident edge $e(l)$. Since the parent $p$ of $l$ now has only one child remaining (and hence degree two), smooth the tree at $p$ as follows: let $e_1=\{u,p\}$ and $e_2=\{p,v\}$ be the edges incident to $p$, and replace them by a single edge $e=\{u,v\}$ of weight $w_e:=w_{e_1}+w_{e_2}$.

• $\mathrm{■}$

  Fork: for a leaf $l$, connect two new vertices to $l$ by edges of length $0$.

The other player, referred to as the algorithm, responds to each operation by choosing a leaf of $T$ to occupy. If the adversary grows by $h$ the leaf $l$ where the algorithm is located, after the growth the algorithm is located at some point along the edge incident to $l$, at distance $h$ from $l$. Therefore, the algorithm needs to either move back to $l$ or choose a different leaf of $T$. If the adversary deletes the leaf where the algorithm is located, the algorithm has to move to another leaf of $T$. The algorithm pays a cost equal to the total distance it moves, and its goal is to minimize the total cost incurred during the game.

The adversary can end the game after any operation. The algorithm is said to be $\rho$-competitive if it incurs cost at most $\rho \cdot d$, where $d$ is the length of the shortest root-to-leaf path in the evolving tree at the end of the game. The instance of the game is said to have width $k$ if there are at most $k$ leaves which exist at the same time in $T$. The algorithm does not have access to $k$ in advance.

A proof of the following reduction, which was given similarly in [10], can be found in the full version of our paper [17, Appendix F].

To derive $\mathrm{\Phi }(T)$, we follow the intuition from the lower bound construction. The edge $e(T)$ could have been spawned by playing the game with depth $k$ and then contracting everything into a single edge; during this time, ALG could have paid up to $D_k{w}_{e(T)}$.

Next, we bound the cost for switching between $LT$ and $RT$. To simplify our reasoning, suppose that the adversary is only allowed to grow the leaf where the algorithm is currently located. Further suppose that this leaf first grows by the maximal amount for which ALG stays at this leaf, and then it grows by a very small (negligible) additional amount which triggers a switch to a different leaf. Therefore, ALG moves from $LT$ to $RT$ when ALG is in the optimal leaf in $LT$ and the adversary grows this leaf so that ${\text{OPT}}_{LT}=x_k{\text{OPT}}_{RT}$. The algorithm pays ${\text{OPT}}_{LT}+{\text{OPT}}_{RT}$ for switching, of which ${\text{OPT}}_{LT}$ is for backtracking to the shared root of $LT$ and $RT$ and ${\text{OPT}}_{RT}$ for reaching the optimum leaf in $RT$. Suppose ALG is currently located in $RT$. Then, ${\text{OPT}}_{LT}$ stayed the same since the last switch, and we can deduce that the last switch cost ${\text{OPT}}_{LT}(1+1/x_k)$, the previous switch cost ${\text{OPT}}_{LT}(1/x_k+1/x_k^{}{}_{}{}^2)$, and so on. The total switching cost can thus be bounded by

Of course, we swap the roles of $LT$ and $RT$ if ALG is currently in $LT$ instead of $RT$. It remains to bound the cost paid while playing the game at depth $k-1$ in the two subtrees $LT$ and $RT$. To this end, we apply an inductive argument to bound this cost by ${\mathrm{\Phi }}_{k-1}(LT)$ and ${\mathrm{\Phi }}_{k-1}(RT)$, respectively.

Putting everything together, for a non-trivial subtree $S$ of level $i$, we define

where

Note that, if ALG is not in $S$, we defined $\text{OPT}\text{<sup class="ltx\_sup">other</sup>}(S)={\text{OPT}}_{LS}\vee {\text{OPT}}_{RS}$ by following the intuition that the last visited leaf in $S$ was the optimal one.

If $S$ is trivial, we simply define ${\mathrm{\Phi }}_i(S)=D_i{w}_{e(S)}$. We may omit the subscript in $\mathrm{\Phi }$ if it is clear from the context.

When deleting a leaf $l$ together with its incident edge, the edges in the sibling subtree of $l$ get “promoted” to a higher level. Although the promotion helps increase the potential, it may not be enough to counteract the edge deletion, so $\mathrm{\Phi }(T)$ may decrease, as it happens in the example in Fig. 2(a). The decrease of $\mathrm{\Phi }(T)$ is problematic, as it may break the inequality $\text{cost}(\text{ALG})\le \mathrm{\Phi }(T)$.

On the other hand, the potential may increase too much after deletion, violating the inequality $\mathrm{\Phi }(T)\le D_k{\text{OPT}}_T$. Recall that this inequality is satisfied if (6) holds for all subtrees $S$ at level $i$. However, if some $S$ is promoted from level $i$ to $i+1$, (6) may no longer be satisfied, as . This happens in the example in Fig. 2(b), where ${\text{OPT}}_{R{T}_2^{\prime }}>x_3{\text{OPT}}_{L{T}_2^{\prime }}$ (because $a{x}_2>a{x}_3$).

So what went wrong with our derivation of the potential? Note that we implicitly assumed that deletion always occurs in a leaf whose sibling is also a leaf, so only trivial subtrees get promoted. Indeed, the lower bound instance is restricted to this kind of “easy” deletions, and it can be proved that the potential is well-behaved on “easy” deletions. By contrast, in both examples in Fig. 2 we delete a leaf whose sibling is a non-trivial subtree. Indeed, the core difficulty of the problem lies in handling deletions in the general case.

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 instance is not known in advance, we initialize $k:=1$, and we increment $k$ when the depth of $T$ exceeds the current value of $k$.

We denote by $w^0$ and $w$ the edge weights in $T^0$ and $T$, respectively. We denote by $S^0$ a subtree of $T^0$, and by $S$ the subtree corresponding to $S^0$ in $T$.

We will ensure that the following invariant always holds.

We now show how to adapt the potential in order to “forget” parts of the tree.

For a non-trivial subtree $S$ of $T$ of level $i$, define

where

For a trivial subtree $S$, define ${\mathrm{\Phi }}_i(S)=D_i{w}_{e(S)}$.

Note that, as long as ${\text{OPT}}_{LS}\vee {\text{OPT}}_{RS}\le x_i({\text{OPT}}_{LS}\wedge {\text{OPT}}_{RS})$, by Claim 10 below we have

so we recover the same recursive formula for ${\mathrm{\Phi }}_i(S)$ as in the previous version of the potential in (4). Otherwise, if, say, ${\text{OPT}}_{LS}>x_i{\text{OPT}}_{RS}$, the refined potential caps some terms – as if “forgetting” some part of $LS$ so that ${\text{OPT}}_{LS}$ gets reduced to $x_i{\text{OPT}}_{RS}$.

It is also important to note that the subtrees which contain ALG’s location will not have their potential capped, as shown in the following claim.

We will ensure that each edge in the distorted tree $T$ is scaled by a factor between $1$ and some constant $C$. Thus, ${\text{OPT}}_T\le C\cdot {\text{OPT}}_{T^0}$. Moreover, when ALG moves from a leaf to another, we will charge the movement cost according to the distances in $T$ instead of the distances in $T^0$, which means that we are overestimating the cost paid.

In the rest of this section we will prove that

which together with the previous observations and the fact that $D_k=O(2^k)$ (as shown in Section 5.3.6) yields

We denote by $\mathrm{\Delta }\text{cost}(\text{ALG})$ the cost paid in the current operation and by $\mathrm{\Delta }\mathrm{\Phi }(T)$ the increase of the potential in the current operation. To ensure that $\text{cost}(\text{ALG})\le \mathrm{\Phi }(T)$, it suffices to show that $\mathrm{\Delta }\text{cost}(\text{ALG})\le \mathrm{\Delta }\mathrm{\Phi }(T)$ holds for all operations.

For two leaves $l,l^{\prime }\in S$, we denote by ${\text{dist}}_S(l,l^{\prime })$ the distance between $l$ and $l^{\prime }$ in subtree $S$. We denote by $l_{{\text{OPT}}_S}$ the optimal leaf in $S$ (breaking ties arbitrarily).