1 Introduction↩︎

The metrical task system (MTS) problem introduced by Borodin et al. [1] is a general framework that models a wide range of online computing problems, e.g., paging [2] and \(k\)-server [3]. In this problem, one server moves between different points (also called states) in an \(n\)-point metric space to process a sequence of requests that arrive one by one; each request incurs different costs when the server is at different states. The total cost is the sum of the transition cost of moving between different states and the cost of serving the requests. An important special case is the metrical service system (MSS) problem [4] where every request has cost either \(0\) or infinity everywhere in the whole metric space. Note that paging and \(k\)-server are both MSS problems.

Since its introduction almost four decades ago, MTS has been intensively studied on both general metrics and some special classes of metrics. On general metrics, in a series of recent breakthrough results, Bubeck et al. [5] showed that the randomized competitive ratio is \(O(\log^2 n)\) and Bubeck et al. [6] gave a matching existential lower bound¹, refuting the previous widely-believed conjecture of the existence of a logarithmic upper bound. Bubeck et al. [6] also showed a universal lower bound² of \(\Omega(\log n)\), which is also tight in the sense that an \(O(\log n)\) upper bound can be achieved on some special metrics, e.g. uniform metrics [1] and weighted stars [5]. While MSS is a special case of MTS, the best competitive ratio that can be achieved by both deterministic and randomized algorithms for MSS in all cases is asymptotically the same as that of MTS only up to a constant factor.

While many online problems are metrical task systems, the best bounds on their competitive ratios are much lower than those implied by the general worst-case MTS bounds. For instance, while the \(k\)-server problem in an \(N\)-point uniform metric space can be reduced to an MSS instance with \(n = \binom{N}{k}\) states, the randomized competitive ratio is known to be \(O(\log k)\), which is much lower than the lower bound of \(\Omega(\log\binom{N}{k})\) implied by the universal lower bound for MSS with \(\binom{N}{k}\) states. The reason for this discrepancy is because while there are \(2^n - 1\) possible requests in a general \(n\)-state MSS, there are only \(N\) possible requests for a \(k\)-server.

The above example motivates studying the competitive ratio of MTS in terms of a parameter of the set of possible requests, instead of the number of states \(n\). Burley and Irani [7] proposed examining request sequences drawn from a given set. For uniform metrics, they provided a deterministic algorithm with competitive ratio \(O(\log n)\) times the (unknown) best possible competitive ratio. Another example that shows the power of restricting the set of possible requests is the power management problem [8] in which there are only two possible requests and the competitive ratio is \(O(1)\) [9]. For MSS, one parameter that has been studied is the width (e.g. [10]–[12]), which is the maximum size of every requested set. Width is well-motivated as MSS can also be viewed as online set chasing, in the sense that the server needs to move to a state in the feasible set where the cost of the current request is \(0\) rather than \(\infty\), and we only need to consider transition cost while the service cost is zero if the server stays in the feasible set at every step.

1.0.0.0.1 Parametrized MTS.

The parametrized MTS proposed by Bubeck and Rabani [13] studies the number of possible requests as the parameter. In particular, the adversary can only generate requests from a fixed set of \(m\) requests known to the algorithm in advance. On uniform metrics, they showed that the deterministic competitive ratio is \(\Theta(m\log (en/m))\), which is significantly better than the general bound of \(\Theta(n)\). Interestingly, the randomized competitive ratio on uniform metrics is still \(\Theta(\log n)\) even when \(m = 2\). On the other hand, for two-level hierarchically separated tree (HST) metrics, the deterministic competitive ratio is \(\Theta(n)\) and the randomized competitive ratio is \(\Theta(\log n)\), even when \(m\) is constant. In summary, restricting \(m\) only improves the deterministic competitive ratio for uniform metrics, and does not help for two-level HSTs.

1.0.0.0.2 Parametrized MSS.

The more interesting case is parametrized MSS, where parametrization leads to substantial improvements of the competitive ratio from the general case. For MSS, restricting possible requests within a fixed set of size \(m\) improves both deterministic and randomized competitive ratios: for uniform metrics, the deterministic and randomized competitive ratios are both \(\Theta(m)\) and thus significantly better when \(n\gg m\). Another interesting aspect of this result is that deterministic algorithms are essentially as powerful as randomized algorithms, which refutes the folklore that the randomized competitive ratio is polylogarithmic in the deterministic competitive ratio for most problems that can be interpreted as metrical task systems. As for the case of two-level HSTs, there are still gaps between the currently known upper and lower bounds: the deterministic competitive ratio is between \(\Omega(\binom{m}{\lfloor m/2\rfloor})=\Omega(2^{m}/\sqrt{m})\) and \(O(m2^{m})\) and the randomized competitive ratio is at least \(\Omega(2^{\lfloor m/2\rfloor})\).

Bubeck and Rabani [13] proposed the following open problems in the study of parametrized MSS, which involve not only the exact tight bound of the competitive ratio in certain scenarios, but also understanding how restricting the number of possible requests \(m\) can help improve the competitive ratio, e.g., can we devise an online algorithm whose competitive ratio is purely in terms of \(m\) rather than metric space size \(n\), and can we do this for some special classes of metrics like HSTs or even general metrics?

1.1 Our Contributions↩︎

In this paper, we make substantial progress towards understanding the competitiveness of parametrized MSS.

1.1.0.0.1 Weighted stars.

Our first main result answers 1 affirmatively.

The result brings more insight into the foundation of this problem and the power of randomization as well, because it matches the lower bound of \(\Omega(m)\) for randomized algorithms since the uniform metric is a special class of the weighted star. 1 shows that deterministic algorithms are essentially as powerful as randomized algorithms in achieving the best possible competitive ratio of \(O(m)\) on weighted stars, the same as the case for the parametrized metrical service system problem on uniform metrics.

1.1.0.0.2 \(2\)-level HSTs.

Next, we address 2 by settling the randomized competitive ratio on \(2\)-level HSTs. Let \(c_{k,m}\) denote the best possible randomized competitive ratio of the MSS problem that can be achieved on all \(k\)-level HSTs with \(m\) request types:

This theorem contains two separate claims: \(c_{2,m}=O( \binom{m}{\lceil m/2 \rceil})\) (6) and \(c_{2,m}=\Omega( \binom{m}{\lceil m/2\rceil})\) (Theorem 4). The lower bound is existential, in the sense that there exists a \(2\)-level HST and \(m\) request types on it such that no randomized algorithm can achieve a better worst-case competitive ratio on all possible request sequences. 2 improves upon previous upper and lower bounds. Previously, the lower bound of \(\Omega( \binom{m}{\lceil m/2\rceil})\) is only known to hold for deterministic algorithms, and we prove that it also holds for randomized algorithms using a new hard instance.

1.1.0.0.3 Higher level HSTs.

Finally, we turn to 3. Previously, Bubeck and Rabani [13] obtained lower bounds on \(c_{k,m}\) for \(k\geq 3\) by iterating their lower bound construction for \(k = 2\). As a consequence, their lower bound rules out \(O(1)\)-competitive algorithms for \(m \geq 6\). By iterating our construction in the proof of 4 to higher level HSTs, we also obtain improved lower bounds on \(c_{k,m}\) for \(k \geq 3\). The formal theorem statement (5) is somewhat technical so we defer it to 4.1.4 and instead state the following corollary.

Combined with [m2], we conclude that the only open case for Question 3 on HSTs is \(m=3\).

1.1.0.0.4 General metrics.

We resolve 3 on general metrics by the following two complement results.

We first show that a constant competitive ratio cannot be achieved on general metrics when \(m\) is at least \(3\) by the following existential lower bound of \(\Omega(\log n)\):

The proof of [m3] can be found in the Appendix.

On the other hand, a constant competitive ratio can be achieved on general metrics when \(m=2\).

This result follows from the observation that when \(m=2\), we can assume that the input sequence is strictly alternating between two request types, because MSS can be regarded as chasing feasible sets and hence repeating the same request does not incur additional cost. Therefore, the only uncertainty of the input is its total length, and the optimal cost can be expressed as a non-decreasing function of the input length. This observation allows us to apply the Guess-and-Double Method to design a constant-competitive algorithm for general metrics when \(m=2\). The proof details of [m2] can be found in the Appendix.

Therefore, the open problems for 3 now lie on some special classes of metrics, including HSTs that we study in this paper.

1.2 Our Techniques↩︎

1.2.0.0.1 Weighted stars.

In MSS, we can think of a request as the set of states that the server must move to. Bubeck and Rabani [13] use an algorithm that works in phases similar to the classical marking algorithm to provide a \(O(m)\)-deterministic algorithm for parametrized MSS on uniform metrics: in each phase, it moves to an arbitrary state in the intersection of the requests in the phase; if the intersection is empty, the algorithm starts a new phase and moves to an arbitrary requested state. It is clear that any solution needs to move at least once during each phase, and they show that the algorithm moves at most \(m\) times during each phase to prove the upper bound. This method is heavily based on the fact that the metric space is uniform and hence we can simply compare the number of times the algorithm’s server moves with that of the optimal server. It is unclear whether their method can be adapted to solve the problem on weighted stars.

We use a significantly different approach based on an interval covering formulation of the problem and apply the primal-dual method. Each interval corresponds to a consecutive subsequence of requests, and the cost to buy this interval is the minimum possible cost of moving to a state that can satisfy all request types in this subsequence. Our analysis exploits the fact that there are only \(m\) different request types to show that the algorithmic cost is at most \(m\) times the feasible dual solution that we maintain and thus obtain the desired competitive ratio. Our formulation is similar to that in [14] but we exploit the property of MSS requests that allows us to only consider the unique state with minimum cost to satisfy every subsequence, while for MTS we have to consider various costs of serving the same subsequence of requests in \(n\) different states, thus leading to the appearance of \(n\) in the competitive ratio instead of purely in terms of \(m\). We hope that similar methods under the linear programming and primal-dual framework can be adapted to solve the more general parametrized MTS problem.

1.2.0.0.2 Lower bounds on HSTs.

We use the same high-level approach used by Bubeck and Rabani [13] in which a construction for the uniform metric³ is lifted to HSTs of higher levels. The main conceptual difference is in our construction for the uniform metric. In Bubeck and Rabani’s construction, there are \(2^{m/2}\) points, each labeled by a node of the Boolean hypercube \(\{0,1\}^{m/2}\) (we assume \(m\) is even here for simplicity). Each of the \(m\) requests correspond to a an axis-aligned halfspace of the Boolean hypercube. Thus, if we construct a sequence of \(m/2\) requests by picking a random halfspace for each dimension with equal probability, then for each request, the algorithm has to move with probability \(1/2\). On the other hand, the adversary can move to the point in the intersection of the halfspaces. This construction can be lifted to HSTs of higher levels by partitioning the set of all possible labels of the lower level case into pairs of antipodes and treating them as complementary requests.

Our key idea is to use a construction for the uniform metric that has more points. In particular, we use \(\binom{m}{m/2}\) points, each corresponding to an \(\frac{m}{2}\)-sized subset of \([m]\). As a result, when we apply the above lifting process, for every fixed level \(k\) of the HST, there are more subtrees in our construction when \(m\) is sufficiently large. We need to be more careful in our analysis as it is no longer true that each request causes the algorithm to move with constant probability. Instead, we prove that its average is still lower bounded by a positive constant.

2 Preliminaries↩︎

Given a metric space \(\mathcal{M}=(X,d)\) where \(X\) is the set of points and \(d: X\times X\rightarrow \mathbb{R}_{\geq 0}\) is the distance function, a parametrized metrical service system instance consists of an initial location \(s_0 \in X\) of the server and a sequence of requests \(\{\rho_{t}\}_{t\geq 1}\), where each \(\rho_{t}\) is from a fixed collection \(\{K_{1},\ldots, K_{m}\}\) of \(m\) non-empty subsets of \(X\). Upon the arrival of a request \(\rho_{t}=K_{i}\) for some \(1\leq i\leq m\) at every step \(t\geq 1\), one must move the server to some state \(s_{t}\in K_{i}\) to maintain a feasible solution if its previous state \(s_{t-1}\) does not satisfy this, and the decision must be made without knowing future requests after \(\rho_{t}\). As a result, MSS can be regarded as the online set chasing problem, illustrating that we always need to move the server to a state in the current requested set, and the parametrized setting restricts that there are only \(m\) different request types. The cost of a solution \(\{s_{t}\}_{t\geq 1}\)is defined to be \[\sum_{t\geq 1} d(s_{t-1},s_{t}),\] where \(d(s_{t-1},s_{t})\) denotes the transition cost to move from \(s_{t-1}\) to \(s_{t}\) upon the arrival of \(\rho_{t}\). This can be interpreted as the total length of the trajectory of the server.

A randomized algorithm \(\mathcal{A}\) has competitive ratio \(c\) if there exists some constant \(\beta\) that is independent of the input sequence (it might depend on the metric space \(\mathcal{M}\)) such that for every input sequence \(\boldsymbol{\rho}\): \[\mathbb{E}[\mathrm{cost}_{\mathcal{A}}(\boldsymbol{\rho})]\leq c\cdot \mathrm{cost}^{*}(\boldsymbol{\rho})+\beta,\] where \(\mathbb{E}[\mathrm{cost}_{\mathcal{A}}(\boldsymbol{\rho})]\) is the expected cost of \(\mathcal{A}\) on input \(\boldsymbol{\rho}\) and \(\mathrm{cost}^{*}(\boldsymbol{\rho})\) is the minimum cost among all feasible solutions of \(\boldsymbol{\rho}\). If \(\beta=0\), then we say that \(c\) is a strict competitive ratio of \(\mathcal{A}\). When we talk about the competitive ratio of a problem class (e.g. parametrized MSS with \(m\) requests on a class of metrics), we are referring to the best possible competitive ratio that can be achieved by some algorithm \(\mathcal{A}\) on all possible inputs from this problem class.

3 Weighted Stars↩︎

On every weighted star metric, there is one root node to which every leaf node (state) is connected with a single edge of non-negative weight. Let \(d_{s}\) denote the weight of the edge between state \(s\) and the root, then the distance between two different states \(s_{1}\) and \(s_{2}\) is \(d(s_{1},s_{2})=d_{s_{1}}+d_{s_{2}}\), where \(d_{s_{1}}\) can be charged as the cost of leaving state \(s_{1}\) and \(d_{s_{2}}\) can be charged as that of entering state \(s_{2}\) if the server moves from \(s_{1}\) to \(s_{2}\).

A common practice on weighted stars is that instead of charging the cost of both leaving \(s_{1}\) and entering \(s_{2}\), we only need to consider the cost of entering the new state at every step, i.e. we can regard the cost of moving from \(s_{1}\) to a different state \(s_{2}\) as only \(d_{s_{2}}\), for both the algorithmic cost and the optimal solution. Over the entire process, the number of times that the server leaves any state is the same as the number of times that the server enters the same state, except for the initial and the last state. Now we formally show that this setting will only lose the competitive ratio of the original problem setting by a factor of at most \(2\).

3.0.0.0.1 State labels.

In this setting, we do not need to consider the initial state. Moreover, each state can be labeled with a subset of \([m]=\{1,2,\ldots,m\}\), which implies the set of request types that are feasible at this position. To formalize, given the label \(S\subseteq[m]\) of some state \(s\) and \(\{K_{1},\ldots,K_{m}\}\) of the parametrized MSS setting of \(m\) possible request types as subsets of the metric space, \(S=\{i\mid s\in K_{i}\}\). We may use the notations of a state \(s\) and its label \(S\) interchangeably, as well as a set of natural numbers and the set of request types \(K_{i}\)’s whose indices are in this set.

3.0.0.0.2 Assumptions.

It suffices to consider \(2^{m}-1\) states that correspond to \(2^{m}-1\) different non-empty subsets of \([m]\), since if there are at least two states with exactly the same label, then any reasonable algorithm should only visit the one whose edge to the node has the minimum weight. For every non-empty \(S \subseteq [m]=\{1,2,\ldots,m\}\), we use \(d_{S}\) to denote the minimum edge weight between the root and any node whose label is exactly equal to \(S\). If no such node exists, just set \(d_{S}=\infty\).

We now make another assumption, which is without loss of generality, yet important for the validity of the algorithm that we are going to propose.

Otherwise, if there exist two different non-empty subsets \(S\) and \(S'\) of \([m]\) such that \(S\subseteq S'\) yet \(d_{S}>d_{S'}\), then every visit to state \(S\) can be replaced by a visit to state \(S'\), maintaining the feasibility because \(S'\supseteq S\) while only reducing the cost. In this case, we can set \(d_{S}\) to \(d_{S'}\) instead, which does not increase the optimal cost since we are only reducing edge lengths, while the algorithmic solution can replace each visit to \(S\) with one visit to \(S'\) in the original setting, which means that every algorithm can be transformed into one whose cost in the original setting is no more than that under this assumption.

We make one final assumption. Against any deterministic algorithm, one can assume that the adversary always forces the algorithm to move to a different state at every step as long as there is some \(K_{i}\) such that the current state of the algorithm is not in \(K_{i}\), and the input ends when the current state is in the intersection of all \(K_{i}\)’s for \(1\leq i\leq m\), if such a scenario exists. A straightforward consequence of this assumption on our problem setting is that any two consecutive requests from the input sequence are of different types, but we will eventually use a stronger argument that also exploits the algorithmic decisions seen by the adversary in the deterministic model to bound the desired competitive ratio.

3.0.0.0.3 Integer programming formulation.

Under the input sequence \(\{\rho_{t}\}_{t\geq 1}\), we use \(S_{i,j}\) to denote the set of request types that appear in the subsequence \(\rho_{i},\ldots, \rho_{j}\), i.e. \(S_{i,j}=\{\ell\mid K_{\ell}=\rho_{t} \text{ for some }i\leq t\leq j\}\), which also corresponds to a unique node of the weighted star in our notation. Then we can write down an integer programming formulation of the problem whose minimum objective function value is a lower bound of the optimal solution of the original problem. We use \(T\) to express the number of steps of the whole input sequence.

\[\label{linear} \begin{array}{ll@{}ll} \text{minimize} & \displaystyle\sum\limits_{1\leq i\leq j\leq T}d_{S_{i,j}}x_{i,j} &\\ \text{subject to}& \displaystyle\sum\limits_{i\leq t\leq j}x_{i,j}\geq 1, &\forall 1\leq t \leq T\\ & x_{i,j} \in \{0,1\}, &\forall 1\leq i\leq j\leq T \end{array}\tag{1}\]

The next step is to write down the dual program of the linear relaxation of (1 ), whose maximum value is no more than the minimum value of its primal linear program and thus the minimum value of the original program (1 ) as well:

\[\label{dual} \begin{array}{ll@{}ll} \text{maximize} & \displaystyle\sum\limits_{1\leq t\leq T}y_{t} &\\ \text{subject to}& \displaystyle\sum\limits_{t:i\leq t\leq j}y_{t}\leq d_{S_{i,j}}, &\forall 1\leq i\leq j\leq T\\ & y_{t}\geq 0, &\forall 1\leq t\leq T \end{array}\tag{2}\]

3.0.0.0.4 Primal-dual algorithm.

We are now ready to state our primal-dual algorithm. Our algorithm maintains a feasible dual solution and at every step \(t\): increases the dual variable \(y_{t}\) until some dual constraint becomes tight, and then decides which state to move to depending on the tight dual constraint.

Upon the arrival of request \(\rho_{t}\), increase the value of the dual variable \(y_{t}\) from the initial value \(0\) until some dual constraint is tight, i.e. \[\sum_{\ell=i}^{t}y_{\ell}=d_{S_{i,t}}\] for some \(i\leq \ell\leq t\); or equivalently, we can write the value as \[\label{primaldualequation} y_{t}=\min_{1\leq i \leq t} \left\{d_{S_{i,t}}-\sum_{\ell=i}^{t-1}y_{\ell}\right\},\tag{3}\] where the value of \(\sum_{\ell=i}^{t-1}y_{\ell}\) is defined to be zero for \(i=t\).

If the tight dual constraint is \(\sum_{\ell=i}^{t}y_{\ell}=d_{S_{i,t}}\), then the algorithm moves the server to the state labeled with \(S_{i,t}\) (the one with the minimum edge weight to the root based on our previous assumption), to process request \(\rho_{t}\). Ties are broken in an arbitrary way.

3.0.0.0.5 Algorithm analysis.

We first prove that the algorithm indeed maintains a feasible dual solution.

Now we are ready to use values of \(y_{t}\)’s that the algorithm computes under its execution to provide an upper bound of its cost.

1 4 and the fact that the maximum value of the linear dual program (2 ) is no more than the minimum value of the original program (1 ) imply Theorem 1.

4 Randomized Competitive Ratio on HSTs↩︎

In this section, we consider hierarchically separated trees (HSTs), a highly symmetric rooted tree structure where the edge weights between a node and all its children are equal. The path between one internal node to all leaves in the subtree rooted at this node has the same number of edges, meaning that the level of a node as the number of edges from it to any of its descendant leaf is well-defined (the level of every leaf node is \(0\)). Moreover, the edge weight between an internal node and all its children is a function of the node level. Since we regard all leaf nodes as the points in the metric space induced by a rooted tree, the distance between two points is a function of the level of their lowest common ancestor. We say that an HST is a \(k\)-level HST if its root is at level \(k\).

The bulk of this section is devoted to proving our lower bounds in 4.1. We finish with the tight upper bound for 2-level HSTs in 4.2.

4.1 Iterative Lower Bounds↩︎

The key ingredient for our improved lower bounds is a new construction for uniform metrics (i.e. \(1\)-level HSTs). Thus, we begin in 4.1.1 by giving the construction and analysis for uniform metrics. Then, we show how to lift our ideas to construct higher level HSTs in 4.1.2. In 4.1.3, we prove our improved lower bound \(c_{2,m}=\Omega(\binom{m}{ \lceil m/2\rceil})\) on \(2\)-level HSTs. Finally, we prove our lower bounds for higher level HSTs.

4.1.0.0.1 Iterative sequence.

We first introduce the following iterative sequence which will be used to express the constructions of hard instances and the lower bounds: \[\label{eq:iter} A_{1,m}=\binom{m}{\lceil m/2\rceil}, \qquad A_{k,m}=\binom{A_{k-1,m}}{\lceil A_{k-1,m}/2\rceil} \quad for k\geq 2.\tag{4}\]

4.1.0.0.2 Labels and requests.

In this section, the requests are defined by assigning a label \(S \subseteq [m]\) to each leaf node. The request type \(K_i\) (as a feasible set) is then defined to be the leaf nodes whose labels contain \(i\), i.e. request type \(K_i\) is served by moving to a node \(v\) whose label \(S\) contains \(i\). We may use number \(i\) to refer to request type \(K_i\) when the context is clear, especially when we use the corresponding subset of \([m]\) to refer to a set of request types.

4.1.0.0.3 Randomized lower bounds.

To prove a lower bound of \(\alpha\) on the competitive ratio of randomized online algorithms, we use Yao’s minimax principle [15], and give a distribution over input instances such that every deterministic algorithm has expected competitive ratio at least \(\alpha\).

In the following, we will only describe and analyze a randomized input sequence whose length is a function of \(k\) and \(m\). This process can be repeated to generate arbitrarily many rounds and hence the request sequence can be arbitrarily long and have arbitrarily large cost.

4.1.1 Warm-up: Uniform Metrics↩︎

We begin with a warm-up on a \(1\)-level HST (uniform metric) which we will lift to higher level HSTs.

4.1.1.0.1 Lower bound instance.

The key property of our \(1\)-level HST is that for every request sequence that is a permutation of \([m]\), there is a leaf that can serve the first \(\left\lceil \frac{m}{2}\right\rceil\) requests and another leaf that can serve the remaining requests, and thus there is always a solution that moves at most twice. Define the \(1\)-level HST structure \(\mathcal{T}_{1,m}\) as follows: it has \(\binom{m}{\lceil m/2\rceil }=A_{1,m}\) leaves, each labeled with a \(\left\lceil \frac{m}{2}\right\rceil\)-size subset of \([m]\) and the distance between every two leaves is \(1\). The adversarial request sequence is a uniform random permutation of \([m]\).

Before we start our analysis, we prove the following proposition which will be useful in bounding the expected cost of the algorithm.

4.1.2 Lifting to Higher Levels↩︎

For every \(k\) and \(m\), we construct an HST \(\mathcal{T}_{k,m}\) to lower bound \(c_{k,m}\).

4.1.2.0.1 Key property of \(\mathcal{T}_{k,m}\).

The key property of \(\mathcal{T}_{1,m}\) and the distribution of request sequences is that for every request sequence in the support of the distribution, there is a leaf that can serve the first half of the requests, and another leaf that can serve the second half. Thus, there is a solution that only moves twice. We generalize this to \(\mathcal{T}_{k,m}\) as follows. The distribution of request sequences and \(\mathcal{T}_{k,m}\) have the property that for every sequence in the support of the distribution, there are two “safe" \((k-1)\)-level subtrees such that there is a low-cost solution that can serve the first half of the request sequence in one of them and the second half in the other. In other words, the low-cost solution only moves twice between \((k-1)\)-level subtrees.

4.1.2.0.2 Higher-level labels.

In our construction of \(\mathcal{T}_{k,m}\), we will assign labels to all nodes except the root. The labels for leaves come from the set \(\mathcal{P}_{0}:=\binom{[m]}{\lceil m/2\rceil}\)⁴. The labels for \(\ell\)-level nodes are collections of those for \((\ell-1)\)-level nodes as follows: Let \(\mathcal{P}_{\ell}\) be the set of \(\ell\)-level labels, then \(\mathcal{P}_{\ell}:=\binom{\mathcal{P}_{\ell-1}}{\lceil|\mathcal{P}_{\ell-1}/2|\rceil }\) for every \(1\leq \ell\leq k-1\). It is easy to see that \(|\mathcal{P}_{\ell}|=A_{\ell+1,m}\). We also define the label of a subtree to be the label of its root node.

4.1.2.0.3 Construction of \(\mathcal{T}_{k,m}\).

For \(k \geq 2\), the HST \(\mathcal{T}_{k,m}\) is constructed iteratively in a top-down fashion as follows. For every label \(P \in \mathcal{P}_{k-1}\), the root of the HST has a child labeled \(P\). For every level \(k-1\geq \ell \geq 1\), every level-\(\ell\) node \(v\) has \(|P(v)|\) children where \(P(v)\) is its label, each given a unique label \(p \in P(v)\).⁵ We remark that there is exactly one level-\((k-1)\) node per label in \(\mathcal{P}_{k-1}\) but for \(\ell < k-1\), there are several level-\(\ell\) nodes from different \((\ell+1)\)-level subtrees that share the same label. For every \(1\leq \ell\leq k\), the distance between every two leaves whose lowest common ancestor is on level \(\ell\) is \(C_{\ell-1}\)⁶ (\(C_{0}=1\)), where \(C_{\ell}\)’s depend on \(k\) and \(m\) and will be defined later in 4.1.4.

4.1.3 Lower Bound Sequence for \(\mathcal{T}_{2,m}\)↩︎

We now prove our lower bound of \(c_{2,m}\). Recall that \(C_1\) is the distance between two leaves in different \(1\)-level subtrees, and \(\mathcal{P}_0\) is the set of all \(\lceil m/2\rceil\)-size subsets of \([m]\). For each label \(S \in \mathcal{P}_0\), define \(\boldsymbol{\rho}(S)\) to be an arbitrary permutation of \(S\).

Now we describe the adversarial randomized input sequence. The adversary first samples a uniformly random permutation \(\{S_{t}\}_{t=1}^{|\mathcal{P}_0|}\) of \(\mathcal{P}_{0}\) and then proceeds in \(|\mathcal{P}_0|=A_{1,m}\) phases as follows: in phase \(t\), it repeats the sequence \(\boldsymbol{\rho}(S_{t})\) for \(C_{1}\) times. Thus, the entire input is a concatenation of all those phases: \[\underbrace{\boldsymbol{\rho}(S_1), \ldots, \boldsymbol{\rho}(S_1)}_{\text{C_1 times}}, \underbrace{\boldsymbol{\rho}(S_2), \ldots, \boldsymbol{\rho}(S_2)}_{\text{C_1 times}},\ldots, \underbrace{\boldsymbol{\rho}(S_{|\mathcal{P}_0|}), \ldots, \boldsymbol{\rho}(S_{|\mathcal{P}_0|})}_{\text{C_1 times}}.\]

For every \(1\leq t\leq A_{1,m}\), we use \(T^{1}_{t-1}\) to denote the label of the \(1\)-level subtree in which the state of the algorithm is located right before the beginning of the phase \(t\).

Since the two lemmata that we have just proven hold for every value \(C_{1}\), we can set it to be some value such that \(C_{1}=\omega (A_{1,m})\) with both values regarded as functions of \(m\), and the desired lower bound immediately follows.

4.1.4 General Iterative Lower Bounds on Higher Levels↩︎

We now prove the lower bound on \(c_{k,m}\) for \(k \geq 3\) expressed with the iterative sequence \(\{A_{k,m}\}_{k\geq 1}\) defined in 4 at the beginning of 4.1.

1 now follows from 5 and [iterdiv].

4.1.4.0.1 Sequences of labels.

We have provided the construction of \(\mathcal{T}_{k,m}\) for every \(k\), and now we need to describe the adversary’s strategy to generate a randomized input sequence on which no deterministic algorithm achieves competitive ratio better than \(c_{k,m}\). Recall that every sequence in the support of the randomized input on \(\mathcal{T}_{2,m}\) is a concatenation of sequences \(\boldsymbol{\rho}(S)\) for labels \(S\in \mathcal{P}_{0}\). Now we want to generalize this concept, the sequence of a label, to every level-\(\ell\) label (i.e. every element of \(\mathcal{P}_{l}\)).

We define inductively on \(\ell\) with \(\ell = 0\) as the base case. For every \(\ell\geq 1\) and every label \(T^{\ell}\in \mathcal{P}_{\ell}\), the sequence \(\boldsymbol{\rho}(T^{\ell})\) is constructed in \(|T^{\ell}|\) phases as follows. Let \(T^{\ell-1}_1,\ldots,T^{\ell-1}_{|T^\ell|}\) be an arbitrary permutation of \(T^\ell\). During each phase \(1 \leq t \leq |T^\ell|\), the sequence \(\boldsymbol{\rho}(T^{\ell-1})\) is repeated consecutively for \(\tfrac{C_{\ell}}{C_{\ell-1}}\) (we can choose values of \(C_{\ell}\)’s to make this amount always an integer at the end) times, and the entire sequence \(\boldsymbol{\rho}(T^{\ell})\) is a concatenation of those phases: \[\underbrace{\boldsymbol{\rho}(T^{\ell-1}_{1}), \ldots, \boldsymbol{\rho}(T^{\ell-1}_{1})}_{\text{\frac{C_{\ell}}{C_{\ell-1}} times}}, \underbrace{\boldsymbol{\rho}(T^{\ell-1}_{2}), \ldots, \boldsymbol{\rho}(T^{\ell-1}_{2})}_{\text{\frac{C_{\ell}}{C_{\ell-1}} times}},\ldots, \underbrace{\boldsymbol{\rho}(T^{\ell-1}_{|T^{\ell}|}), \ldots, \boldsymbol{\rho}(T^{\ell-1}_{|T^{\ell}|})}_{\text{\frac{C_{\ell}}{C_{\ell-1}} times}}.\]

We now define another iterative sequence \(\{B_{\ell}\}_{1\leq\ell \leq k-1}\) and show that it can be used to express the upper bound of the optimal solution of the request sequences: \[\begin{align} B_{1}=\left\lceil \frac{A_{1,m}}{2}\right\rceil, \qquad B_{\ell}=\left\lceil\frac{A_{\ell,m}}{2}\right\rceil \left[(B_{\ell-1}+C_{\ell-2})\cdot\frac{C_{\ell}}{C_{\ell-1}}+C_{\ell-1}\right] \quad for 2\leq \ell\leq k-1. \end{align}\]

4.1.4.0.2 Adversary’s strategy and analysis

We are finally ready to describe the adversary’s strategy on \(\mathcal{T}_{k,m}\). It first samples a uniformly random permutation \(\{T^{k-2}_{t}\}_{t=1}^{A_{k-1,m}}\) of \(\mathcal{P}_{k-2}\) (note that \(|\mathcal{P}_{k-2}|=A_{k-1,m}\)), and then proceeds in \(A_{k-1,m}\) phases: in each phase \(t\), \(\boldsymbol{\rho}(T^{k-2}_{t})\) is repeated consecutively for \(\frac{C_{k-1}}{C_{k-2}}\) times, and the whole input is the concatenation of all \(A_{k-1,m}\) phases.

It remains to show that there exist possible values of \(C_{\ell}\)’s and \(B_{\ell}\)’s for \(1\leq\ell\leq k-1\) such that \(C_{k-1}=\omega(B_{k-1})\) as \(m\) tends to infinity⁷. This would show that the randomized competitive ratio on \(\mathcal{T}_{k,m}\) is at least \(\Omega(\frac{A_{k-1,m}C_{k-1}}{C_{k-1}+B_{k-1}})=\Omega(A_{k-1,m})\) as a function of \(m\).

Let \(C_{1}=\omega(\prod_{j=1}^{k-1}A_{j,m})\) and \(C_{\ell}=\omega( (\prod_{j=\ell}^{k-1}A_{j,m})C_{\ell-1})\) for \(2\leq \ell\leq k-1\). We now prove that such a sequence satisfies the desired property.

This completes the proof of Theorem 5.

4.2 Tight Upper Bound for 2-Level HSTs↩︎

The idea to show a general upper bound for \(2\)-level HSTs is as follows: even if there is no restriction on the size of the whole tree itself, some leaves and subtrees are redundant in the sense that any reasonable solution should not move to them, or does not need to move to them while maintaining feasibility and not increasing the cost. As a result, we can trim off those redundant nodes and hence reduce the graph size, just as how we show that we only need to consider \(2^{m}-1\) states for the weighted star case. This idea has also been applied by Bubeck and Rabani to give iterative upper bounds for \(2\) and higher levels of HSTs (see Section 4.2 Deeper Trees in [13]), and we present a refined argument on \(2\)-level HSTs that closes the gap between upper and lower bounds. We show that the number of leaves remained after such preprocessing is bounded in terms of \(m\) and apply the optimal MTS algorithm for HSTs from [5].

Since the initial state can be arbitrarily given, in this part we only consider those leaves different from the initial state, to evaluate whether some states can be totally replaced by others and every algorithm can still maintain a feasible solution with equal or less cost. This is without loss of generality up to a constant factor, since there is only one initial state and thus it is sufficient to give an upper bound of the amount of states that are not the initial state.

In this part, we express leaf nodes lexicographically by a tuple \((S,T)\) where \(S\) is the label of the leaf node itself and \(T\) is the label of the \(1\)-level subtree that it is in. The label of every node is defined in the same way as the previous subsection⁸ . A preliminary observation is that, if two leaf nodes share exactly the same tuple, then they are isomorphic and it suffices to only keep one in the tree. The feasibility of removing redundant nodes is that, when \(m\) possible requests and their corresponding feasible sets in the whole metric are fixed, running an algorithm over a subset of states produces a feasible solution for the whole metric as well, therefore what we need to show is that the optimal cost does not increase while we trim off some states.

As a result, we can assume that every \(1\)-level subtree is an antichain over subsets of \([m]\), which contains at most \(\binom{m}{\lceil m/2\rceil }=A_{1,m}\) elements according to Sperner’s theorem [16]. The next thing is to consider the maximum amount of such \(1\)-level subtrees, which is equivalent to the amount of antichains over subsets of \([m]\). This amount is called Dedekind number \(D(m)\) and its following asymptotic approximation property has been proven in [17]:

5 Chasing Two Sets on General Metrics↩︎

In this section, we consider the case \(m=2\), where there are only two possible request types \(K_{1}\) and \(K_{2}\) that can be generated by the adversary, and show that there is a constant-competitive algorithm that works on general metrics, with no requirement on the size \(|X|\) nor the structure of the metric space.

Our method is an application of the Guess-and-Double Method. Here we address that our algorithm is strictly competitive without an additive constant. This matters when \(m=2\) because it is trivial to design a non-strictly \(1\)-competitive algorithm in this case: suppose \(s_{1}\in K_{1}\) and \(s_{2}\in K_{2}\) are the points such that \(d(s_{1},s_{2})=d(K_{1},K_{2})\), then the algorithm can move to \(s_{1}\) upon the first request of \(K_{1}\) and then always alternate between \(s_{1}\) and \(s_{2}\) upon every new request, and it is easy to see that the cost of this algorithm is no more than the optimal cost plus the diameter of the metric space. As a result, we can apply the Guess-and-Double Method to eliminate the additive constant and devise a strictly competitive algorithm.

5.1 Counterexample to Greedy↩︎

Before we show how to apply the Guess-and-Double Method to our problem setting, we first use a simple example to see how the classical ski rental problem can be reduced to our problem, which denies the attempt of applying the greedy algorithm that always moves to the closest feasible state from the current one.

Example 1. Suppose that we have a ski rental instance where the rental rate is \(1\) and the buying cost is \(B>1\). At every new step of the online instance, if the algorithm has not bought the ski set yet, then it needs to either rent it for one more step with cost \(1\), or buy it with cost \(B\). After buying the ski set, the algorithm does not need to pay new cost no matter how many steps are there in the future.

Consider a metric space where there are four points \(s_{0},s_{1},s_{2},s_{3}\) such that \(d(s_{0},s_{1})=d(s_{1},s_{2})=d(s_{0},s_{2})=1\) and \(d(s_{i},s_{3})=B\) for \(i=0,1,2\). We construct two sets \(K_{1}\) and \(K_{2}\) such that \(K_{1}=\{s_{1},s_{3}\}\) and \(K_{2}=\{s_{2},s_{3}\}\). The initial location of the server is at \(s_{0}\). \(s_{3}\) here is the safe location for both \(K_{1}\) and \(K_{2}\), which corresponds to the state of the ski rental instance after buying the ski set with cost \(B\).

The input sequence of the two-set chasing problem instance that we construct is just \(K_{1}\) and \(K_{2}\) alternating. It is easy to see that if the server has not moved to the safe location \(s_{3}\) with cost \(B\) at some step, then every time when a new request appears, it always needs to switch between \(s_{1}\) and \(s_{2}\) with cost \(1\). This is exactly equivalent to the two-state ski rental problem. Moreover, we can also see from this reduction that the simple memoryless greedy algorithm to move to the closest feasible state at every step has unbounded competitive ratio when the input sequence is sufficiently long, since it pays cost \(1\) at every step and never visits \(s_{3}\).

5.2 Our Algorithm↩︎

Without loss of generality, suppose that the first request in the sequence that forces the algorithm to move is \(K_{1}\) and hence the whole sequence can be regarded as \(K_{1},K_{2},K_{1},K_{2}\ldots\), strictly alternating between two sets. In this way, \(s_{0}\notin K_{1}\) holds. We further assume that \(d(s_{0},K_{1})=\min_{s\in K_{1}}d(s_{0},s)= 1\), which means that the cost of the optimal solution is always at least \(1\) as long as the input sequence is non-empty. Moreover, if there is only one time step in the input sequence, then the optimal solution is exactly \(1\).

Since the sequence is essentially in the alternating form \(K_{1},K_{2},K_{1},K_{2}\ldots\), the only variable we have to deal with is the length of the sequence. Longer the sequence, bigger the value of the optimal solution, and at every step we have a lower bound of the optimal solution which is exactly that of the partial sequence that has appeared so far. To formalize, Let \(\mathrm{OPT}_{t}\) be the cost of the optimal solution for the server to process the tasks that have arrived up to and including step \(t\). At every step \(t\) we maintain a guess of an integer \(j\geq 0\) such that

\[2^{j}\leq \mathrm{OPT}_{t}<2^{j+1}.\]

Moreover, we can compute the input sequence with the largest number of steps whose optimal value is in the range \([2^{j}, 2^{j+1})\) for each non-negative integer \(j\), and let \(\widehat{\mathrm{OPT}}_{j}\) be the optimal solution of serving this sequence. We slightly abuse similar notations by using them to refer to both the solution itself and the cost value of it. Note that if \(2^{j}\leq \mathrm{OPT}_{t}<2^{j+1}\) for some \(t\), then \(s_{t}(\widehat{\mathrm{OPT}}_{j})\), the state of \(\widehat{\mathrm{OPT}}_{j}\) at step \(t\), is well-defined, because the length of the sequence for which \(\widehat{\mathrm{OPT}}_{j}\) is defined is at least \(t\) based on our choice of the longest possible one. Our algorithm always moves to \(s_{t}(\widehat{\mathrm{OPT}}_{j})\) as we have defined at every step \(t\).

We divide the whole process into phases according to the values \(j\)’s that are used in the Guess-and-Double Method where each phase contains all steps when the value \(j\) stays a given value (see the description of Algorithm 1 for details). Suppose that there are \(k\) phases in total chronologically with values \(j_{1},...,j_{k}\) respectively, then the final optimal solution has value \(2^{j_{k}}\leq\mathrm{OPT}<2^{j_{k}+1}\), according to the definition of the guessed value \(j\). When the algorithm moves from state \(s_{t}(\widehat{\mathrm{OPT}}_{j_{\ell}})\) to \(s_{t+1}(\widehat{\mathrm{OPT}}_{j_{\ell}})\) within the same phase with the guessed value \(j_{\ell}\), we charge the cost \(d(s_{t}(\widehat{\mathrm{OPT}}_{j_{\ell}}), s_{t+1}(\widehat{\mathrm{OPT}}_{j_{\ell}}))\) to the internal cost of the \(l\)’th phase; when it moves from \(s_{t}(\widehat{\mathrm{OPT}}_{j_{\ell}})\) to \(s_{t+1}(\widehat{\mathrm{OPT}}_{j_{\ell+1}})\) between two different phases, we first use the triangle inequality to give an upper bound \[d(s_{t}(\widehat{\mathrm{OPT}}_{j_{\ell}}), s_{t+1}(\widehat{\mathrm{OPT}}_{j_{\ell+1}}))\leq d(s_{t}(\widehat{\mathrm{OPT}}_{j_{\ell}}), s_{0})+d(s_{0}, s_{t+1}(\widehat{\mathrm{OPT}}_{j_{\ell+1}})),\] and then charge \(d(s_{0}, s_{t+1}(\widehat{\mathrm{OPT}}_{j_{\ell+1}}))\) to the internal cost of the \((\ell+1)\)’th phase and \(d(s_{t}(\widehat{\mathrm{OPT}}_{j_{\ell}}), s_{0})\) to the external cost between the \(\ell\)’th and the \((\ell+1)\)’th phase.

Lemma 13. The internal cost of the \(\ell\)’th phase is no more than \(2^{j_{\ell}+1}\) for every \(1\leq \ell\leq k\).

Proof. Suppose that the Guess-and-Double Method stays in the \(\ell\)’th phase from step \(t_{\ell,1}\) to \(t_{\ell,2}\), then the internal cost of this phase can be expressed as \[d(s_{0}, s_{t_{\ell,1}}(\widehat{\mathrm{OPT}}_{j_{\ell}}))+\sum_{t=t_{\ell,1}}^{t_{\ell,2}-1}d(s_{t}(\widehat{\mathrm{OPT}}_{j_{\ell}}),s_{t+1}(\widehat{\mathrm{OPT}}_{j_{\ell}})).\]

Based on our notation of the trajectory of \(\widehat{\mathrm{OPT}}_{j_{\ell}}\) and the definition that it is the longest sequence whose optimal value is strictly less than \(2^{j_{\ell}+1}\), it holds that

\[\sum_{t=0}^{t_{\ell,2}-1}d(s_{t}(\widehat{\mathrm{OPT}}_{j_{\ell}}),s_{t+1}(\widehat{\mathrm{OPT}}_{j_{\ell}}))\leq\widehat{\mathrm{OPT}}_{j_{\ell}}<2^{j_{\ell}+1},\]

where \(s_{0}(\widehat{\mathrm{OPT}}_{j_{\ell}})\) is defined to be the initial state \(s_{0}\). Comparing two trajectories \[s_{0},s_{1}(\widehat{\mathrm{OPT}}_{j_{\ell}}),\ldots,s_{t_{\ell,2}}(\widehat{\mathrm{OPT}}_{j_{\ell}}) \text{ and } s_{0},s_{t_{\ell,1}}(\widehat{\mathrm{OPT}}_{j_{\ell}}),\ldots,s_{t_{\ell,2}}(\widehat{\mathrm{OPT}}_{j_{\ell}}),\] it is easy to see that the latter is a shortcut of the former, and hence the total length of the latter is no more than that of the former, which is no more than \(2^{j_{\ell}+1}\) based on the definition of a phase. ◻

Lemma 14. The external cost between the \(\ell\)’th and the \((\ell+1)\)’th phase is no more than \(2^{j_{\ell}+1}\) for every \(1\leq \ell\leq k-1\).

Proof. If \(t_{\ell,2}\) is the last step of the \(\ell\)’th phase and the Guess-and-Double Method moves to the \((\ell+1)\)’th phase at the next step, then the external cost between the two phases is \(d(s_{0},s_{t_{\ell,2}}(\widehat{\mathrm{OPT}}_{j_{\ell}})\). Since the whole trajectory \(s_{0},s_{1}(\widehat{\mathrm{OPT}}_{j_{\ell}}),\ldots,s_{t_{\ell,2}}(\widehat{\mathrm{OPT}}_{j_{\ell}})\) has length no more than \(2^{j_{\ell}+1}\), the shortcut \(d(s_{0},s_{t_{\ell,2}}(\widehat{\mathrm{OPT}}_{j_{\ell}})\) has length no more than \(2^{j_{\ell}+1}\) based on triangle inequalities. ◻

Theorem 7. The strict competitive ratio of Algorithm 1 on every two-set chasing instance is no more than \(6\).

Proof. The internal cost of each phase with the guessed value \(j_{\ell}\) is at most \(2^{j_{\ell}+1}\), and the total internal cost is no more than

\[\sum_{\ell=1}^{k}2^{j_{\ell}+1}\leq \sum_{\ell=1}^{k}2^{j_{k}+1-k+\ell}=2^{j_{k}+1}\sum_{t=1}^{k}\frac{1}{2^{t-1}}< 2^{j_{k}+2}.\]

Similarly, the total external cost is no more than \(2^{j_{k-1}+2}\leq 2^{j_{k}+1}\). The algorithmic execution terminates in phase \(k\) with guessed value \(j_{k}\), so the final optimal solution is at least \(2^{j_{k}}\), and 1 achieves strict competitive ratio of no more than \(\frac{2^{j_{k}+2}+2^{j_{k}+1}}{2^{j_{k}}}=6\). ◻

The Guess-and Double Method for the two-set chasing problem (parametrized metrical service system with \(m=2\)) can be generalized to the case where every possible request sequence is an unknown prefix of some fixed sequence that the algorithm knows in advance. In this case, the only uncertainty is the length of the actual input sequence, and \(\widehat{\text{OPT}}_{j}\) for every \(j\geq 0\) can be computed prior to the execution of the algorithm. Although the research of metrical task systems has been focused on finite discrete metrics (and the majority of the classic results express the competitive ratio as a function of the number of points \(n\)), this Guess-and Double Method actually works for every general metric space including the Euclidean space etc., since it only requires that every \(\widehat{\text{OPT}}_{j}\) can be computed prior to the execution of the algorithm, which is guaranteed by that every possible request sequence is some prefix of a given infinite sequence, and that the triangle inequalities of the metric space hold.

6 Open Problems↩︎

Following the initial study of parametrized metrical task systems (MTS) and metrical service systems (MSS) by Bubeck and Rabani [13], our research answers several open problems posed by Bubeck and Rabani. We provide a deterministic \(O(m)\)-competitive algorithm on weighted stars, tighten the gap between the upper and lower bounds of randomized competitive ratios on HSTs of different levels, and show that it is possible to design a strictly constant-competitive algorithm on general metrics when \(m=2\). However, multiple problems remain open: as 3 has been resolved on general metrics by showing the contrast between \(m=2\) and \(m=3\) cases, the focus is now on special classes of metrics, e.g., is it possible to obtain a finite competitive ratio for chasing \(3\) sets on HSTs or line metrics? Another interesting open problem is whether the \(O(\binom{m}{\lceil m/2\rceil})\) upper bound of randomized algorithms on \(2\)-level HSTs can also be achieved by a deterministic algorithm. The progress on this problem will not only close the gap between the upper and lower bounds known for deterministic algorithms for this particular class of metrics, but also deepen our fundamental understanding of the parametrized MSS problem, as it concerns whether deterministic algorithms are essentially as powerful as randomized algorithms on \(2\)-level HSTs and other classes of metrics. Moreover, the technique that we use in 3 is a linear programming primal-dual method that exploits the properties of parametrized MSS with \(m\) request types, and we wonder whether this framework can be generalized to prove the results of the more general parametrized MTS on uniform metrics (the tight deterministic bound of \(\Theta(m\log(en/m))\) was proven by Bubeck and Rabani) or weighted stars (no result yet).

References↩︎

---

1. The existential lower bound means that there exist \(n\)-point metrics on which the lower bound holds.↩︎

2. The universal lower bound means that it holds for every \(n\)-point metric space.↩︎

3. A \(1\)-level HST is equivalent to a uniform metric.↩︎

4. The notation \(\binom{S}{k}\) means the collection of all \(k\)-size subsets of \(S\).↩︎

5. Recall that \(P(v)\), a label of a level-\(\ell\) node, is a collection of level-(\(\ell-1\)) labels.↩︎

6. We always assume that \(C_\ell/C_{\ell-1}\) is an integer for every \(\ell\geq 1\) .↩︎

7. Here both \(C_{k-1}\) and \(B_{k-1}\) are functions of \(m\). When we consider both \(m\) and \(k\) as constants, the lower bound can be achieved by setting the ratio \(C_{\ell}/C_{\ell-1}\) sufficiently large for every \(1\leq\ell\leq k-1\) and the proof idea is similar.↩︎

8. Recall that the label of a leaf node is the set of request types that this state can satisfy, and the label of a \(1\)-level subtree is the set of labels of leaf nodes contained in it.↩︎