Lower bounds for MTS

Consider a rooted tree $T=(V,E)$ with leaf set $\mathcal L\subseteq V$ and positive vertex weights $w : V\setminus \mathcal L\to \mathbb R_+$ that are non-increasing along root-leaf paths. We recall the ultrametric $d_w$ defined on $\mathcal L$ by

$d_w(\ell,\ell') \mathrel{\vcenter{:}}= w(\mathrm{lca}(\ell,\ell')).$

Say that $(\mathcal L,d_w)$ is a $\tau$ -HST metric for some $\tau \geq 1$ if $\mathcal L$ is the leaf set of some weighted tree $T=(V,E)$ , and $d_w$ is the ultrametric corresponding to a weight $w$ on $T$ with the property that $w(y) \leq w(x)/\tau$ whenever $y$ is a child of $x$ . (So for a finite metric space, the notions of $1$ -HST metric and ultrametic are equivalent.) Say that $(\mathcal L,d)$ is a strict $\tau$ -HST metric if we require the stronger property that $w(y)=w(x)/\tau$ whenever $x,y \in V$ are internal nodes and $y$ is a child of $x$ .

Two metrics $d$ and $d'$ on a set $X$ are $K$ -equivalent if there is a constant $c > 0$ such that

$d(x,y) \leq c\, d'(x,y) \leq K d(x,y)\qquad \forall x,y \in X\,.$ We leave the following statements as an exercise: For every

$\tau > 1$ , every

$1$ -HST is

$\tau$ -equivalent to some strict

$\tau$ -HST.

There is a constant $C \geq 1$ such that if $(\mathcal L,d_w)$ is a $C (\log n)^2$ -HST metric, where $n=|\mathcal L|$ , then the competitive ratio for MTS on $(\mathcal L,d_w)$ is $\Omega\left(\log n\right)$ .

While the preceding theorem applies only to

$\tau$ -HSTs with

$\tau$ sufficiently large, the next lemma shows how we can improve the separation parameter by passing to a subset of leaves.

If $(\mathcal L,d)$ is a strict $2$ -HST, then for every $k \in \mathbb N$ , there is a subset $\mathcal L' \subseteq \mathcal L$ with

$|\mathcal{L}'| \geq |\mathcal{L}|^{1/k},$

and such that

$(\mathcal L', d)$ is a

$2^k$ -HST metric.

Combining this with Theorem 1 yields:

If $(\mathcal L,d)$ is a $1$ -HST metric with $n=|\mathcal L|$ , then the competitive ratio for MTS on $(\mathcal L,d)$ is at least $\Omega\left(\frac{\log n}{\log \log n}\right)$ .

Recall that the Metric Ramsey theorem from the preceding lecture implies that every $n$ -point metric space contains a subset of size $\sqrt{n}$ that is $O(1)$ -equivalent to a $1$ -HST. This yields:

For every $n$ -point metric space, the competitive ratio for MTS is at least $\Omega(\log n/\log \log n)$ .

We will not prove Theorem 1, but we will prove a lower bound for two special cases that together capture the essential elements of the full argument. The general case is discussed at the end.

The complete d-ary tree

The first case we’ll consider is when $T$ is a $d$ -ary tree of height $h$ , so that $|\mathcal L|=d^h$ . Define $w(x)=\tau^{-\mathrm{dist}_T(x,r)}$ , where $r$ is the root of $T$ and $\mathrm{dist}_T$ denotes the combinatorial distance on $T$ . Then $(\mathcal L,d_w)$ is a $\tau$ -HST.

Our goal is to establish a lower bound of $\Omega(h \log d)$ on the competitive ratio for MTS when $\tau$ is sufficiently large. Note that when $\tau = \Theta(1)$ and $d=2$ , it is an open problem to exhibit an $\Omega(h)$ lower bound, and proving such a bound is likely the most difficult obstacle in obtaining an $\Omega(\log n)$ lower bound for every $n$ -point ultrametric.

Our costs functions will be of the form $\{\epsilon\cdot c_\ell : \ell \in \mathcal L\}$ , where $\epsilon> 0$ is a number, and

$c_\ell(\ell') = \begin{cases} 0 & \ell=\ell' \\ 1 & \ell \neq \ell'\,. \end{cases}$ More succinctly:

$c_\ell \mathrel{\vcenter{:}}= \mathbf{1}-\mathbf{1}_\ell$ .

Let $\alpha_h$ be the competitive ratio for height $h$ . We will prove inductively that $\alpha_h \geq \Omega(h \log d)$ .

Consider first the case $h=1$ . We define the height- $1$ cost sequence. The root $r$ has $d$ leaves beneath it. We do the following $d \log d$ times: Choose a random leaf $\ell$ and play the cost function $c_\ell$ . It is straightforward that if $\mathrm{alg}_1$ denotes the cost of an online algorithm, then:

$\mathbb{E}[\mathrm{alg}_1] \geq \log d\,.$ (Note that if a cost comes at

$\ell$ , then the algorithm must either move and pay movement cost

$1$ , or stay in place and pay service cost

$1$ .)

Consider the following offline algorithm: Move to the leaf that will be chosen the smallest number of times, and stay there. The movement cost if $1$ , and a standard coupon collecting argument shows that the service cost is $O(1)$ , hence:

$\mathbb{E}[\mathrm{opt}_1] \leq O(1)\,.$ We conclude that the competitive ratio satisfies

$\alpha_1 \geq c \log d$ for some

$c > 0$ .

Consider now the case of $h \geq 2$ . We define the height- $h$ cost sequence. The root has beneath it $d$ subtrees $T_1, T_2, \ldots, T_d$ of height $h-1$ . For some number $\mu_h$ to be chosen shortly, we do the following $\mu_h d$ times: Choose $i \in \{1,2,\ldots,d\}$ uniformly at random and play in $T_i$ the height- $(h-1)$ cost sequence scaled by $1/\tau$ .

Consider first what an online algorithm can do. If the algorithm’s state lies in $T_i$ when a height- $(h-1)$ cost sequence is imposed on $T_i$ , it can either leave at some point during the sequence, or it can remain in . Hence the algorithm pays at least $\min\left(1,\tau^{-1} \mathbb{E}[\mathrm{alg}_{h-1}]\right)$ . It follows that:

$\mathbb{E}[\mathrm{alg}_h] \geq \mu_h \min\left(1,\tau^{-1} \mathbb{E}[\mathrm{alg}_{h-1}]\right) \geq \mu_h \min\left(1,\tau^{-1} \alpha_{h-1} \mathbb{E}[\mathrm{opt}_{h-1}]\right)\,.$

Thus if

$\begin{equation}\label{eq:tauchoice} \tau \geq \alpha_{h-1} \mathbb{E}[\mathrm{opt}_{h-1}]\end{equation}$

it holds that

$\begin{equation}\label{eq:alg} \mathbb{E}[\mathrm{alg}_h] \geq \mu_h \tau^{-1} \alpha_{h-1} \mathbb{E}[\mathrm{opt}_{h-1}]\,.\end{equation}$ We will choose

$\tau$ so that

$\eqref{eq:tauchoice}$ holds.

Let us now analyze an offline algorithm. Let $\rho_i$ denote the number of times that $T_i$ is chosen. The offline algorithm first moves to some $T_i$ with $\rho_i$ minimal, and then plays optimally against level- $(h-1)$ cost sequences arriving in $T_i$ .

If $\mu_h \geq \Omega(\log d)$ , then the normal approximation to a binomial distribution shows that there is a constant $0 < c' < 1$ such that

$\mathbb{E}\left[\min(\rho_1,\ldots,\rho_d)\right] \leq \mu_h - c'\sqrt{\mu_h \log d}\,.$ Hence incorporating the movement cost yields:

$\mathbb{E}[\mathrm{opt}_h] \leq 1 + \left(\mu_h - c'\sqrt{\mu_h \log d}\right) \tau^{-1} \mathbb{E}[\mathrm{opt}_{h-1}]\,.$

We now choose $\mu_h$ so that

$c' \sqrt{\mu_h \log d} \tau^{-1} \mathbb{E}[\mathrm{opt}_{h-1}] = 2\,,$ i.e.,

$\mu_h \mathrel{\vcenter{:}}= \frac{4}{\log d} \left(\frac\tau{c' \mathbb{E}[\mathrm{opt}_{h-1}]}\right)^2$ Note from

$\eqref{eq:tauchoice}$ , we have

$\begin{equation}\label{eq:muh} \mu_h \geq \frac{4}{(c')^2\log d} \alpha_{h-1}^2.\end{equation}$ Since

$\alpha_{h-1} \geq \alpha_1 \geq \Omega(\log d)$ it follows that

$\mu_h \geq \log d$ for

$c'$ chosen small enough. (In particular, the normal approximation applies.)

Our choice of $\mu_h$ ensures that

$\begin{align} \mathbb{E}[\mathrm{opt}_h] &\leq \left(\mu_h-\frac{c'}{2} \sqrt{\mu_h \log d}\right) \tau^{-1} \mathbb{E}[\mathrm{opt}_{h-1}] \label{eq:opt}\end{align}$ Combining this with

$\eqref{eq:alg}$ yields

$\alpha_h \geq \frac{\mathbb{E}[\mathrm{alg}_h]}{\mathbb{E}[\mathrm{opt}_h]} \geq \frac{\alpha_{h-1}}{1-\frac{c'}{2} \sqrt{\frac{\log d}{\mu_h}}} \geq \alpha_{h-1} \left(1+\frac{c'}{2} \sqrt{\frac{\log d}{\mu_h}}\right),$

where the latter inequality holds because

$c' < 1$ and

$\mu_h \geq \log d$ . Using

$\eqref{eq:muh}$ , this gives

$\alpha_h \geq \alpha_{h-1} + \frac{c'}{2} \log d\,,$ completing the argument.

Note that in $\eqref{eq:tauchoice}$ , we required . So let us use $\eqref{eq:opt}$ to compute:

$\mathbb{E}[\mathrm{opt}_h] \leq \mu_h \tau^{-1} \mathbb{E}[\mathrm{opt}_{h-1}] \leq \frac{O(1)}{\log d} \frac\tau{\mathbb{E}[\mathrm{opt}_{h-1}]}$ Since

$\mathbb{E}[\mathrm{opt}_h] \cdot \mathbb{E}[\mathrm{opt}_{h-1}] \leq O(\tau/\log d)\,,$ and

$\mathbb{E}[\mathrm{opt}_h] \geq \mathbb{E}[\mathrm{opt}_{h-1}] \geq 1$ for all

$h$ , it follows that

$\mathbb{E}[\mathrm{opt}_h] \leq O(\sqrt{\tau/\log d})$ , meaning that

$\tau \geq \alpha_{h-1} \mathbb{E}[\mathrm{opt}_{h-1}]$ will be satisfied for

$\tau \geq C(\alpha_{h-1}/\log d)^2 \asymp h^2$ . Since

$h \asymp \frac{\log n}{\log d}$ , this yields completes the proof of in the special case of a

$d$ -regular HST.

The “superincreasing” metric

We will now consider a highly unbalanced family of HSTs. These were analyzed in a paper of Karloff, Rabani, and Ravid.

Let us define the trees $\{T_n\}$ as follows: The root $r_{n}$ of $T_n$ has two children. The left child is a copy of $T_{n-1}$ of rooted at $r_{n-1}$ , and the right child is a single leaf. We denote $w_n(r_n)=1$ , and $w_n(r_{n-1}) = 1/\tau_n$ , where $\tau_n > \tau_{n-1} > \cdots > 0$ is a sequence of positive weights we will choose soon, and such that $\tau_n \leq O(\log n)$ .

The basic structure of our argument will be similar to the $d$ -regular case. We do the following $2 \mu_n$ times: Choose $i \in \{L,R\}$ uniformly at random. If $i=L$ , we play a height- $(n-1)$ cost sequence on the left subtree (scaled by $1/\tau_n$ ). Otherwise, we play $c_\ell$ , where $\ell$ is the leaf constituting the right subtree.

Consider an online algorithm. If the algorithm sits in the left subtree when $i=L$ , then either the algorithm moves out of the subtree (movement cost $1$ ), or it incurs the cost of a height- $(n-1)$ inductive sequence scaled by $1/\tau_n$ . If it sits in the right subtree, then it pays cost $1$ (either by moving or staying and incurring the service cost). If we choose $\tau_n \mathrel{\vcenter{:}}=\alpha_{n-1} \mathbb{E}[\mathrm{opt}_{n-1}]$ , then such an algorithm always pays at least $\tau_n^{-1} \alpha_{n-1} \mathbb{E}[\mathrm{opt}_{n-1}]$ in any of these cases. Therefore:

$\begin{equation}\label{eq:algn} \mathbb{E}[\mathrm{alg}_n] \geq \mu_n \tau_n^{-1} \alpha_{n-1} \mathbb{E}[\mathrm{opt}_{n-1}]. \end{equation}$

We now bound the cost of the optimal offline algorithm. Let $\rho_L$ be the number of times $i=L$ and let $\rho_R \mathrel{\vcenter{:}}= 2\mu_n - \rho_L$ . The algorithm will always sit by default in the left subtree. If $\rho_R=0$ , it will move to the right subtree, suffer zero service cost there, and then move back to the left subtree (paying total cost $2$ ). If $\rho_R > 0$ , the algorithm will remain in the left subtree and play an optimal strategy for $T_{n-1}$ .

This yields:

$\begin{aligned} \mathbb{E}[\mathrm{opt}_n] &\leq \left(1-{\mathbb{P}}[\rho_R=0]\right) \mathbb{E}\left[\rho_L \tau_n^{-1} \mathrm{opt}_{n-1} \mid \rho_R > 0\right] + 2 {\mathbb{P}}[\rho_R=0] \\ &\leq (1-4^{-\mu_n}) \mu_n \tau_n^{-1} \mathbb{E}[\mathrm{opt}_{n-1}] + 2 \cdot 4^{-\mu_n}.\end{aligned}$ Now choose:

$\mu_n \mathrel{\vcenter{:}}=\frac{4 \tau_n}{\mathbb{E}[\mathrm{opt}_{n-1}]} = 4 \alpha_{n-1}\,.$ This yields:

$\mathbb{E}[\mathrm{opt}_n] \leq \left(1-\tfrac12 4^{-4 \alpha_n}\right) \mu_n \tau_n^{-1} \mathbb{E}[\mathrm{opt}_{n-1}].$

Combined with $\eqref{eq:algn}$ , we have

$\alpha_n \geq \frac{\mathbb{E}[\mathrm{alg}_n]}{\mathbb{E}[\mathrm{opt}_n]} \geq \alpha_{n-1} + \tfrac12 4^{-4\alpha_{n-1}}.$ This implies that

$\alpha_n \geq \beta \log n$ for some positive

$\beta < 1$ . (To see this observe, that if

$f(x)=\beta \log x$ , then

$f'(x) = \beta/x < \frac12 4^{-4 \beta \log x}$ for

$\beta$ chosen small enough.)

Note furthermore that

$\mathbb{E}[\mathrm{opt}_n] \leq 4\,,$ and therefore

$\tau_n \leq O(\log n)$ .

The general case

We have demonstrated lower bounds in two cases: When the underlying tree $T$ is regular, and when it is unbalanced and binary. The general case can be proved by combining these two strategies along any $\Omega((\log n)^2)$ -HST. The next lemma contains the basic idea. We leave it to the reader as a basic exercise. (Hint: Use the concavity of $x \mapsto \sqrt{x}$ .)

Suppose that $n=n_1+n_2+\cdots+n_m$ where $n_1 \geq n_2 \geq \cdots \geq n_m \geq 1$ . Then either $\sqrt{n_1}+\sqrt{n_2} \geq \sqrt{n}$ , or there is some $\ell \geq 3$ such that $\ell \cdot \sqrt{n_\ell} \geq \sqrt{n}$ .

Suppose now that $T$ is a rooted tree with subtrees $T_1, T_2, \ldots, T_m$ beneath the root, and such that $T_i$ has $n_i$ leaves with $n_1 \geq n_2 \geq \cdots \geq n_m \geq 1$ . The lemma says we can either consider only the first two subtrees (the binary, possibly “unbalanced” case), or we can take the first $\ell$ subtrees for some $\ell \geq 3$ , prune them so they all have exactly $n_\ell$ leaves, and then prove a lower bound. Analyzing these two cases correspond roughly to the two lower bound arguments above.