Smoothed Analysis of Online Metric Problems

The algorithm controls the movement of $k$ servers located at points in $M$. Each request is a point $r_t\in M$, and must be served by moving one of the servers to $r_t$. The cost of the algorithm is defined as the total distance travelled by all servers.

The algorithm controls the movement of $k$ taxis located at points in $M$. Each request is a pair of points $r_t=(a_t,b_t)\in M^2$, representing the start and destination of a ride request. To serve it, the algorithm must choose a taxi and move it first to $a_t$ and then to $b_t$. The cost is defined as the total distance of “empty runs” (i.e., distance travelled except for the travels from $a_t$ to $b_t$).

The algorithm controls the movement of a single server located in $M$. Each request is a subset $r_t\subset M$ of cardinality at most $k$. To serve it, the algorithm must move the server to one of the points in $r_t$. The cost incurred by the algorithm is the total distance travelled.

Throughout this paper, we assume that the metric space $M$ is a subset of ${ℝ}^m$ and the metric $d$ is induced by a norm, i.e., $d(x,y)=\Vert x-y\Vert$ for all $x,y\in M$, where $\parallel \cdot \parallel$ is an arbitrary norm. We assume that $M$ has bounded diameter, and denote by $B_M$ a (closed) ball of smallest radius containing $M$, and by $R_M$ its radius.

We consider the variant of the problems described above where each request $r_t$ is drawn from some probability distribution $D_t$. These distributions need not be independent, i.e., the distribution $D_t$ (and whether it exists or the sequence stops earlier) can be chosen by the adversary after the realizations of $r_1,\mathrm{\dots },r_{t-1}$ have been determined (however, without knowledge of any random choices made by the online algorithm). For the $k$-server problem, $D_t$ is a distribution over $M$, for the $k$-taxi over $M^2$ and for chasing small sets over $M^{k_t}$ for some $k_t\le k$. We denote by $D_{ti}$ the corresponding marginal distributions, where $i=1$ for $k$-server, $i\in \{1,2\}$ for $k$-taxi and $i\in [k_t]$ for chasing small sets.

In the absence of any restrictions on the probability distribution, this problem setting is equivalent to the familiar worst-case setting, as the adversary can choose a (degenerate) distribution that places all probability mass on the worst-case request sequence. Thus, we impose the following smoothness assumption:

Equivalently, this means that the density function of each marginal distribution is upper bounded by $1/(\sigma \cdot \mathrm{vol}(B_M))$. The case $\sigma =1$ corresponds to uniformly distributed requests, whereas $\sigma \to 0$ captures the classical worst-case setting.

For a (possibly randomized) algorithm $A$, we denote its expected cost on an instance $I$ by $\mathrm{cost}(A,I)$. Denote by $\mathrm{opt}$ the offline algorithm that achieves the lowest possible cost on any instance. In the classical (worst-case) setting, an online algorithm is said to be $c$-competitive if

for all possible instances $I$, where $\alpha$ is a constant independent of $I$. We say that $A$ is $c$-competitive on $\sigma$-smooth instances if inequality (1) holds when $I$ is sampled as a $\sigma$-smooth instance and both sides of the inequality are replaced by their expectation over the randomness in $I$. We allow $\mathrm{opt}$ to serve the actual realization of the instance optimally, i.e., knowing the outcome of the random sampling process of $I$ in advance. Of course, any competitive algorithm in this setting is also competitive if $\mathrm{opt}$ has to make its choices before knowing the outcomes of the future sampling process of $I$.

We will usually drop $I$ from the notation when it is understood from the context.

An $\eta$-net of a metric space $M$ is a subset $N\subseteq M$ satisfying the following properties:

• $\mathrm{■}$

  $N$ is $\eta$-dense in $M$: For all $x\in M$ there exists $y\in N$ such that $d(x,y)\le \eta$.

• $\mathrm{■}$

  $N$ is $\eta$-separated: For all $x,y\in N$ it holds that $d(x,y)>\eta$.

The aspect ratio of a metric space is the ratio between the largest and smallest non-zero distance.

Denote by ${\mathrm{opt}}_M$ and ${\mathrm{opt}}_N$, respectively, an optimal offline algorithm for the instance in $M$ and the projected instance in $N$. By assumption

for some constant $\alpha$. Denote by $T$ the number of requests and by $𝔼[T]$ its expectation¹¹1$T$ may be random as the adversary can choose the stopping point depending on the realizations of earlier requests.. As argued above,

with the additional cost due to movement between $\pi (r_t)$ and $r_t$ at each time. By a similar argument,

as a possible offline algorithm to service the requests $\pi (r_1),\pi (r_2),\mathrm{\dots },\pi (r_T)$ in $N$ is to always be in the configuration of ${\mathrm{opt}}_M$ projected onto $N$, incurring at most an additional cost $2\eta$ per request by the triangle inequality (noting that, without loss of generality, ${\mathrm{opt}}_M$ moves at most one server/taxi per time step). Combining inequalities (2), (3) and (4) gives

Next, we make use of the assumption that the optimal offline cost is at least $\mathrm{\Omega }(\eta )$ amortized per request in expectation, i.e., $\mathrm{cost}({\mathrm{opt}}_M)\ge \mathrm{\Omega }(\eta )\cdot 𝔼[T]-\beta$ for some constant $\beta$. Substituting this into the previous inequality gives

and the lemma follows since the additive term $\eta \cdot k+\alpha +𝒪(\beta \cdot c_N)$ is a constant independent of the request sequence. $◀$

The proof is similar to [25, Claim 2.6]. We initialize $N$ as a singleton set containing an arbitrary point from $M$; then as long as there exists a point $x\in M$ such that $d(x,y)>\eta$ for all $y\in N$, we add $x$ to $N$. By construction, $N$ is an $\eta$-net. Moreover, the balls of radius $\eta /2$ centered at the points in $N$ are disjoint and contained in a ball of radius $R_M+\eta /2$ (namely, the ball obtained by extending the radius of $B_M$ by $\eta /2$). The ratio between the volume of a ball of radius $\eta /2$ and the ball of radius $R_M+\eta /2$ is ${\left(\frac{\eta /2}{R_M+\eta /2}\right)}^m$. Thus, there can be at most ${\left(\frac{R_M+\eta /2}{\eta /2}\right)}^m\le {\left(\frac{3R_M}{\eta }\right)}^m$ disjoint balls. $◀$

Let $\eta =3R_M\cdot {\left(\frac{\sigma }{\mathrm{poly}(k)}\right)}^{1/m}$, where $\mathrm{poly}(k)$ is the function from Proposition 6. Then $A_M$ is $𝒪(c_N)$-competitive by Proposition 6 and Lemma 7. If $\eta >R_M$, then $N$ can be chosen as the singleton containing only the center of the ball $B_M$, which trivially yields $c_N=1$ and the theorems. Otherwise, by Lemma 8 the size of the $\eta$-net $N$ is

and since the diameter of $M$ is at most $2R_M$, the aspect ratio of $N$ is

Thus, since $c_N=𝒪({\log }^{2}k\cdot \log n)$ for $k$-server [14, 15], $c_N=𝒪({\log }^3\mathrm{\Delta }\cdot {\log }^2(nk\mathrm{\Delta }))$ for $k$-taxi [32], and $c_N=O({\log }^{2}n)$ for metrical task system [13, 19], and chasing small sets is a special case of metrical task systems (in the same metric space), the result follows. $◀$

We note that the competitive ratio for $k$-taxi could actually be improved by a factor $1/\min {\{m,\log (k/\sigma )\}}^3$. (Note that the $\log \mathrm{\Delta }$ term stands for a quantity that is at least 1, so the improvement is not greater.) This would typically only yield a constant factor improvement though, considering practical applications of the $k$-taxi problem usually having a small dimension of at most $3$.

Since chasing small sets in a metric space $(M,d)$ is a metrical task system in the same metric space, we can invoke the above theorem with $ϵ=1$, $\mathrm{\ell }=\lceil {\log }_{2}k\rceil +1$ and using as $A_i$ for $i=1,\mathrm{\dots },\mathrm{\ell }-1$ our algorithm with smoothness parameter ${\sigma }_i=2^{-2^i}$, and as $A_{\mathrm{\ell }}$ the $\mathrm{\Theta }(k^2)$-competitive algorithm from [11] for chasing small sets in the fully adversarial setting.

Since $\mathrm{diam}\le 2R_M$, the additive term in Theorem 10 is a constant independent of the request sequence. Thus, the resulting algorithm achieves, up to a factor $1+ϵ\le 2$, the same competitive ratio as the best of the algorithms $A_i$. If the true smoothness parameter , then $𝒪(\min \{k^2,{\log }^2(k/\sigma )\})$-competitiveness follows since the minimum is attained by $k^2$. Otherwise, there exists $i$ such that ${\sigma }_i\le \sigma \le \sqrt{{\sigma }_i}$. Since any $\sigma$-smooth instance is also ${\sigma }_i$-smooth, we achieve competitive ratio $𝒪({\log }^2(k/{\sigma }_i))=𝒪({\log }^2(k/\sigma ))$. This yields Theorem 4.

For the $k$-server problem (Theorem 2), the same argument works since $k$-server can be modelled as a metrical task system in the space of server configurations (whose diameter is $k$ times the diameter of the original metric space). The only difference is that the algorithm $A_{\mathrm{\ell }}$ for general metrics in the fully adversarial setting has competitive ratio $\mathrm{\Theta }(k)$ [38].

It is not known how to model the $k$-taxi problem as a metrical task system, due to configuration changes that incur no cost.²²2Though it belongs to the more general class of metrical task systems with transformation [10]. Nonetheless, the proof of Theorem 10 in [8] extends to this setting without any change, so we can still apply the same combination method also to the $k$-taxi problem. However, since no competitive algorithm for the $k$-taxi problem on general metrics in the fully adversarial setting is known, we require a lower bound on $\sigma$ to ensure that the number of combined algorithms is finite.

Let $\delta >0$. Consider a subsequence $r_{t+1},r_{t+2},\mathrm{\dots },r_{t+4k}$ of $4k$ consecutive requests. For $i=0,\mathrm{\dots },4k$, we denote by $S_i$ a $\delta$-separated subset of $\{r_{t+1},r_{t+2},\mathrm{\dots },r_{t+i}\}$, constructed as follows: $S_0=\mathrm{\varnothing }$, and for $i\ge 1$,

Note that $S_i=S_{i-1}$ if and only if $r_{t+i}$ belongs to a ball of radius $\delta$ centered at a point in $S_{i-1}$. The volume of each such ball is at most a ${\left(\frac{\delta }{R_M}\right)}^m$ fraction of the volume of $B_M$, and thus its probability under $D_{t+i}$ is at most ${\left(\frac{\delta }{R_M}\right)}^m/\sigma$. Hence, since there are at most $4k$ such balls of radius $\delta$, the probability that $S_i=S_{i-1}$ is bounded as

We now choose $\delta =R_M\cdot {\left(\frac{\sigma }{8k}\right)}^{1/m}$, so that the right hand side becomes $1/2$. In other words, in each step, another point is added to $S_i$ with probability at least $1/2$. Thus, after $4k$ steps we have $|S_{4k}|\ge 2k$ with probability at least $1/2$. If this is the case, then any offline algorithm must pay at least $k\cdot \delta$ to serve these requests, regardless of the configuration it starts at: Indeed, at most $k$ of the requests in $S_{4k}$ can be served by a server that previously served no other request from $S_{4k}$. For the remaining $|S_{4k}|-k\ge k$ requests, the serving server must have moved at least distance $\delta$ since the previous time it served a request from $S_{4k}$, since $S_{4k}$ is $\delta$-separated. Thus, any subsequence of $4k$ consecutive requests contributes $k\cdot \delta /2$ to the expected optimal cost. Over a sequence of $T$ requests, this leads to an expected optimal cost of

$◀$

We proceed similarly to the proof of Lemma 11, except in the construction of $S_i$ we add a request $r_{t+i}=(a_{t+i},b_{t+i})$ if its start location $a_{t+i}$ is more than distance $\delta$ from the destinations of all the requests $r_{t+1},\mathrm{\dots },r_{t+i-1}$:

Again,

as $S_i=S_{i-1}$ requires $a_{t+i}$ to fall in one of at most $4k$ balls of radius $\delta$. As before, the same choice of $\delta$ yields $|S_{4k}|\ge 2k$ with probability at least $1/2$. If this is the case, then any offline algorithm must pay at least $k\cdot \delta$ to serve these requests: At least $|S_{4k}|-k\ge k$ of the requests in $S_{4k}$ are served by a taxi that also served a previous request since time $t+1$, incurring cost at least $\delta$ by definition of $S_{4k}$. The lemma is then concluded in an identical fashion to the proof of Lemma 11. $◀$

Let $\delta >0$. Consider two consecutive request sets $r_{t-1}$ and $r_t$. The probability that the $i$th point in $r_{t-1}$ is within distance $\delta$ from the $j$th point in $r_t$ is at most $\frac{1}{\sigma }{\left(\frac{\delta }{R_M}\right)}^m$. Thus, by a union bound over the at most $k^2$ pairs of points in $r_{t-1}\times r_t$, the probability that some point in $r_{t-1}$ is within distance $\delta$ from some point in $r_t$ is at most $\frac{k^2}{\sigma }{\left(\frac{\delta }{R_M}\right)}^m$. Otherwise, with probability at least $1-\frac{k^2}{\sigma }{\left(\frac{\delta }{R_M}\right)}^m$, any offline algorithm must pay at least $\delta$ at time $t$ to move from $r_{t-1}$ to $r_t$. Choosing $\delta =R_M\cdot {\left(\frac{\sigma }{2k^2}\right)}^{1/m}$, we see that the probability is at least 1/2. Thus, the expected offline cost is at least $\frac{\delta }{2}=\frac{R_M}{2}\cdot {\left(\frac{\sigma }{2k^2}\right)}^{1/m}$ per time step. $◀$