# Boosting Double Coverage for k-Server via Imperfect Predictions

Alexander Lindermayr, Nicole Megow, Bertrand Simon

► To cite this version:

Alexander Lindermayr, Nicole Megow, Bertrand Simon. Boosting Double Coverage for k-Server via Imperfect Predictions. Algorithmica, 2025, 87 (11), pp.1477-1517. 10.1007/s00453-025-01333-9. hal-05390451

HAL Id: hal-05390451

https://hal.science/hal-05390451v1

Submitted on 1 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

Check for
updates

# Boosting Double Coverage for *k*-Server via Imperfect Predictions

Alexander Lindermayr¹ · Nicole Megow¹ · Bertrand Simon²

Received: 25 October 2023 / Accepted: 9 June 2025 / Published online: 10 July 2025

© The Author(s) 2025

## Abstract

We study the online *k*-server problem in a learning-augmented setting. While in the traditional online model, an algorithm has no information about the request sequence, we assume that there is given some advice (for example, machine-learned predictions) on an algorithm’s decision. There is, however, no guarantee on the quality of the prediction, and it might be far from being correct. Our main result is a learning-augmented variation of the well-known Double Coverage algorithm for *k*-server on the line (Chrobak et al. in SIAM J Discret Math 4(2):172–181, 1991) in which we integrate predictions as well as our trust into their quality. We give an error-dependent worst-case performance guarantee, which is a function of a user-defined confidence parameter, and which interpolates smoothly between an optimal performance in case that all predictions are correct, and the best-possible performance regardless of the prediction quality. When given good predictions, we improve upon known lower bounds for online algorithms without advice. We further show that our algorithm achieves for any *k* almost optimal guarantees, within a class of deterministic learning-augmented algorithms respecting *local* and *memoryless* properties. Our algorithm outperforms a previously proposed (more general) learning-augmented algorithm. It is noteworthy that the previous algorithm crucially exploits memory, whereas our algorithm is *memoryless*. Finally, we demonstrate in experiments the practicability and the superior performance of our algorithm on real-world data.

**Keywords** Online k-server problem · Competitive analysis · Advice · Imperfect predictions · Learning-augmented algorithms · Consistency · Robustness

<footnote>A subset of the results has been presented at the 13th Innovations in Theoretical Computer Science Conference (ITCS) 2022 [38].</footnote>

<footnote>Extended author information available on the last page of the article</footnote>
# 1 Introduction

The $k$-server problem is one of the most fundamental online optimization problems. Manasse et al. [44, 45] introduced it in 1988 as a generalization of other online problems, such as the prominent paging problem, and since then, it has been a cornerstone for developing new models and techniques. We follow this line and investigate the $k$-server problem in the recently evolving framework of learning-augmented online algorithms [39, 46].

We consider the $k$-server problem on the line in which there are given $k$ distinct servers $s_1, \dots, s_k$. At any point in time, the servers positions on the real line $\mathbb{R}$ are characterized by a configuration, that is, an element of $\mathbb{R}^k$. In the beginning, the servers are given in some initial configuration $C_0 \in \mathbb{R}^k$. A sequence of requests $r_1, \dots, r_n \in \mathbb{R}$ is revealed online one-by-one, that is, an algorithm only knows the current (unserved) request, serves it, and only then sees the next request; it has no knowledge about future requests and cannot revert previous decisions. To serve a request, at least one server must move to the requested point. The cost of serving a request $r$ is defined as the total distance traveled by the server(s) since the arrival of $r$ and until it is served. The task is to give an online strategy of minimum total cost for serving a request sequence.

We analyze algorithms for this problem in the framework of competitive analysis. Therein, an online algorithm $\mathcal{A}$ is called $\mu$-competitive if, for every initial configuration $C_0$, there exists a constant $c \ge 0$ such that for every instance $I$ starting in $C_0$, it holds that $\mathcal{A}(I) \le \mu \cdot \text{OPT}(I) + c$, where $\mathcal{A}(I)$ denotes the cost of $\mathcal{A}$ on $I$ and $\text{OPT}(I)$ the cost of an optimal offline solution for $I$. The competitive ratio of $\mathcal{A}$ is the smallest $\mu$ such that $\mathcal{A}$ is $\mu$-competitive.

Manasse et al. [45] gave a strong lower bound that rules out any deterministic online algorithm for the $k$-server problem with a competitive ratio better than $k$. They also stated the famous $k$-server conjecture in which they conjecture that there is a $k$-competitive online algorithm for the $k$-server problem in any metric space and for any $k$. The conjecture has been proven to be true for special metric spaces such as the line [23], considered in this paper, the uniform metric space (paging problem) [51], and tree metrics [22]. For the $k$-server problem on the line, Chrobak et al. [23] devised the DOUBLECOVERAGE algorithm, and proved the best-possible competitive ratio $k$. For a given request, DOUBLECOVERAGE moves the (at most) two adjacent servers towards the requested point until the first of them reaches that point. Chrobak and Larmore extended this algorithm to tree metrics, again achieving the optimal competitive ratio of $k$ [22].

The past decades have witnessed a rapid advancement of machine learning (ML) methods, which nowadays can be expected to predict often—but not always—uncertain data with good accuracy. The lack of guarantees on the predictions and the need for trustable performance guarantees led to the area of learning-augmented (online) algorithms [46]. This recently emerging research area investigates online algorithms that have access to predictions, for example, on parts of the instance or the algorithm's actions, while not making any assumption on the quality of the predictions. We introduce a prediction error $\eta \ge 0$ that quantifies a prediction's quality for a fixed instance. Here $\eta = 0$ shall refer to the case where the prediction is correct. An algo-

<figure><img src="image_3.png" /></figure>
rithm does not know what quality a prediction has, but we can use it in the analysis to measure an algorithm’s performance as a function of η. If a learning-augmented algorithm is μ(η)-competitive for some function μ, we say that the algorithm is α-consistent if α ≥ μ(0) and β-robust if μ(η) ≤ β for any prediction error η [42, 47]. The consistency ratio of a learning-augmented algorithm is the smallest α such that the algorithm is α-consistent. The robustness ratio is defined analogously.

Antoniadis et al. [6] proposed learning-augmented online algorithms for general metrical task systems, a generalization of our problem. Their algorithm relies on simulating several online algorithms in parallel and keeping track of their solutions and cost. This technique crucially employs additional *memory* which can be a serious drawback in practice when decisions must be made without access to the history.

In this work, we introduce memory-constrained learning-augmented algorithms for the *k*-server problem on the line. Intuitively, an algorithm *A* is *memory-constrained*, if the decision for the next move of *A* only depends on the current situation (server positions, request and prediction). It is especially independent of previous requests assuming a fixed current situation. However, as the algorithm is allowed to move a server to any point of the real line, it could use its position to encode any information at a negligible cost. This issue is often addressed by forbidding algorithms to move several servers per request (hence, restricting to so-called *lazy* algorithms), which leads to the classical *memoryless* property, although variations of this definition exist [36]. A downside of this restriction is that deterministic memoryless algorithms cannot be competitive, and there is no distinction between the type of information gathered by *DOUBLECOVERAGE* and unconstrained information encoding. This difference has been acknowledged by informally considering *DOUBLECOVERAGE* as memoryless [34], although noting immediately that such a definition for a non-lazy algorithm is cumbersome. To allow the behavior of *DOUBLECOVERAGE*, we formally define *memory-constrained* algorithms as algorithms allowed to move several servers without crossings, making decisions independently of previous requests, but with an *erasable* memory: for any set of *k* distinct points and any starting configuration, there exists a finite sequence of requests among these *k* points after which each point contains exactly one server. We will refer to such a sequence as a *force* to these *k* points. This definition is quite general as it allows to pre-move some servers as *DOUBLECOVERAGE* does, and even allows information encoding, but provides a possibility to erase any information gathered. The restriction of crossing servers rules out that an algorithm encodes up to *O*(*k* log *k*) bits via permuting server identities; every algorithm that crosses servers but does not use such information can be simulated by an algorithm that does not cross servers and instead moves multiple servers. The algorithms we design will not abuse any information encoding, but our lower bounds will hold in this context.

## 1.1 Our Contribution

We design learning-augmented memory-constrained online algorithms for the *k*-server problem on the line.

We consider an *action* prediction model that predicts algorithmic choices of an optimal algorithm, that is, predicting which server should serve a certain request.
Given an instance *I* composed of the request sequence *r*₁, ..., *r*ₙ, we define a prediction for *I* as a sequence of indices *p*₁, ..., *p*ₙ from the set {1, ..., *k*}. The intuition is that these correspond to the indices of the servers that a predicted solution uses to serve the requests. Specifically, we assume that this predicted solution is “reasonable” in the sense that it moves only one server per request and no server moves past another server.

If $s_1, \dots, s_k$ are the servers of some learning-augmented algorithm, we call $s_{p_t}$ the predicted server for the $t$-th request. We call the algorithm that simply follows the predictions FTP, that is, it serves each request by the predicted server. We denote its cost by FTP($I$). We define the total prediction error as $\eta = \text{FTP}(I) - \text{OPT}(I)$, where $\text{OPT}(I)$ denotes the cost of an optimal solution for instance $I$. We emphasize that it is sufficient for our algorithms that the $k$th prediction appears together with the $k$th request.

Our main result is a parameterized algorithm for the *k*-server problem on the line with an error-dependent performance guarantee that—when having access to high-quality predictions—beats the known lower bound of *k* on the competitive ratio for deterministic online algorithms. The guarantee is expressed through a parameter $\lambda \in [0, 1]$ that controls the tradeoff between robustness and consistency. It can be viewed as a confidence parameter, which the algorithm user can adjust based on their trust in the prediction quality or according to the desired level of robustness or consistency.

**Theorem 1** Let $\lambda \in [0, 1]$. We define $\beta(0, k) = \infty$, $\beta(\lambda, k) = \sum_{i=0}^{k-1} \lambda^{-i}$, and

$$ \alpha(\lambda, k) = \begin{cases} 1 + 2\lambda + 2\lambda^2 + \dots + 2\lambda^{(k-1)/2} & \text{if } k \text{ is odd, and} \\ 1 + 2\lambda + 2\lambda^2 + \dots + 2\lambda^{k/2-1} + \lambda^{k/2} & \text{if } k \text{ is even.} \end{cases} $$

There exists a learning-augmented memory-constrained online algorithm for the *k*-server problem on the line with a competitive ratio of at most

$$ \min \left\{ \alpha(\lambda, k) \cdot \left(1 + \frac{\eta}{\text{OPT}}\right), \beta(\lambda, k) \right\}. $$

In particular, the algorithm is $\alpha(\lambda, k)$-consistent and $\beta(\lambda, k)$-robust, for any $\lambda > 0$.

Fixing a *k* for both functions illustrates that for varying values of $\lambda$, $\alpha(\lambda, k)$ interpolates monotonously between 1 and *k* while $\beta(\lambda, k)$ grows from *k* as $\lambda$ decreases. This matches our expectation on a learning-augmented online algorithm, as it improves in consistency but loses in robustness compared to the best-possible online algorithm. From another perspective, for a fixed value of $\lambda$, $\alpha(\lambda, k)$ is bounded by a constant (equal to $1 + \frac{2\lambda}{1-\lambda}$) for any *k*, which highlights the algorithm’s strong consistency but comes at the price of an exponential dependency on *k* for $\beta(\lambda, k)$.

To show this result, we design an algorithm that carefully balances between (i) the wish to simply follow the predictions (FTP), which is obviously optimal if the predictions are correct, which is 1-consistent, and (ii) the best-possible online algorithm when not having access to (good) predictions DOUBLECOVERAGE [23], which

<figure><img src="image_4.png" /></figure>
is $k$-robust. An additional challenge is to preserve the memory-constrained property. We achieve this, by generalizing the classical DOUBLECOVERAGE [23] in an intuitive way. Essentially, our algorithm LAMBDADC includes the information about predicted servers and our trust into them by varying server speeds.

The analysis of our algorithm is tight. On the technical side, our analysis builds on the powerful potential function method, as does the analysis of DOUBLECOVERAGE [23]. While LAMBDADC is quite simple (a precise definition follows), the analysis is much more intricate and requires a careful re-design for the learning-augmented setting. Our main technical contribution is the definition and analysis of different parameterized potential functions for proving robustness and consistency that capture the different speeds for moving servers and the accordingly more difficult tracing of the server moves.

We remark that our performance bound also holds (with an additional factor of 2 on the error term) using the error measure of Antoniadis et al. [6], applied to our (specialized) problem. This is shown in [40]. This alternative error definition sums up the distances between the configurations of OPT and FTP after every request and thus, it may seem more intuitive as server positions are compared instead of solution costs. However, our error definition allows us to establish learnability results and also simplifies some analyses.

While our result is tailored to the *k*-server problem, the framework by Antoniadis et al. [6] is designed for more general metrical task systems. Interestingly, one of their methods is a deterministic combination of DOUBLECOVERAGE and FTP, we refer to it as FTP &DC. It is shown that FTP &DC is 9-consistent and 9*k*-robust. Our methods differ substantially. While FTP &DC carefully tracks states and costs of the simulated individual algorithms, LAMBDADC is a simple algorithm that only requires knowledge of the current configuration. Further, LAMBDADC has better guarantees for *k* < 20 and an appropriate parameter $\lambda$ (for example, $k = 19$ and $\lambda = 0.83$), but does not offer such a good tradeoff for larger *k*. Actually, this is unavoidable for a certain class of memory-constrained algorithms, which includes LAMBDADC.

Indeed, we complement our main result with an almost matching lower bound on the consistency-robustness tradeoff. We construct a non-trivial bound for the class of memory-constrained algorithms that satisfy an additional locality property; its precise definition is formulated in Sect. 5. Intuitively, the locality property enforces an algorithm to achieve a better competitive ratio for a subinstance served by fewer servers. Other locality restrictions have been required before to establish lower bounds for other problems, for example, for online matching on the line, see [5]. We show the following result.

**Theorem 2** Let $\lambda \in (0, 1]$, $\rho(\lambda, k) = \sum_{i=0}^{k-1} \lambda^i$, and $\beta(\lambda, k) = \sum_{i=0}^{k-1} \lambda^{-i}$. Let $\mathcal{A}$ be a learning-augmented locally-consistent and memory-constrained deterministic online algorithm for the $k$-server problem on the line. Then, if $\mathcal{A}$ is $\rho(\lambda, k)$-consistent, it has a robustness ratio of at least $\beta(\lambda, k)$.

Algebraic transformations (see Lemma 22) show that $\alpha(\lambda, k) < 2 \cdot \rho(\lambda, k)$, which implies that LAMBDADC achieves a tradeoff within a factor of at most 2 of the optimal consistency-robustness tradeoff (among locally-consistent and memory-constrained
algorithms). For $k = 2$, LAMBDADC achieves the optimal tradeoff (among memory-constrained algorithms).

Further, we briefly address the learnability of our predictions, even though this is not the focus of our work. We show that a *static* prediction sequence is PAC-learnable [52, 53]. We show a bound on the sample complexity that is polynomial in the number of requests, $n$, and the number of servers, $k$, and we give a learning algorithm with a running time that is polynomial in $n$, $k$ and the number of samples.

Finally, we demonstrate the power of our approach in empirical experiments on real-world data. We show that for a reasonable choice of $\lambda$ our method outperforms the classical online algorithm DOUBLECOVERAGE as well as the algorithm by Antoniadis et al. [6] for nearly all prediction errors.

## 1.2 Further Related Work

The past few years have exhibited several demonstrations of the power of learning-augmented algorithms improving on traditional online algorithms. Previously studied online problems related to the *k*-server problem and routing include, for example, caching problems [3, 6, 10, 32, 42, 49] and online graph problems involving routing and exploration [2, 7–9, 12, 29, 54], and many more. While predictions have been most extensively studied in the context of online optimization, learning-augmented algorithms have also shown success in other areas beyond online optimization, for example, to speed up search queries [37] or the running time of algorithms [28] in the context of dynamic algorithms [14, 31], and in mechanism design [1, 30]. For further information, we refer to an introduction by Mitzenmacher and Vassilvitskii [46] and an online paper collection [39].

More than a decade ago, Mahdian, Nazerzadeh, and Saberi [43] demonstrated performance improvements for online allocation algorithms when there is access to an accurate solution estimation. They further bounded the case where the estimation is inaccurate. While these bounds essentially correspond to consistency and robustness, they did not precisely measure the prediction quality. Yet they introduced a parameter to express the tradeoff between both bounds. In the recent field of learning-augmented algorithms, Kumar, Purohit, and Svitkina [47] have initiated the use of a similar parameter $\lambda \in [0, 1]$. It can be interpreted as an algorithm’s indicator of trust in the given predictions: smaller $\lambda$ indicates stronger trust and gives a higher priority to a better consistency at the cost of a worse robustness, and vice versa.

As mentioned, Antoniadis et al. [6] provide a general learning-augmented framework for any metrical task system, which includes the *k*-server problem. Applied to the line metric, they devise a learning-augmented algorithm that crucially requires memory and obtain a 9-consistent and 9*k*-robust algorithm. They also presented an extension to the setting of multiple predictions [4].

The *k*-server problem has been studied also in the context of reinforcement learning (RL), originating at [33] and including hierarchical RL learning [27] as well as deep RL learning [41].

The classical online *k*-server problem without access to predictions has been studied extensively, also in general metric spaces. Koutsoupias and Papadimitriou [35] showed that the WORKFUNCTION algorithm is $(2k-1)$-competitive, which is

<figure><img src="image_5.png" /></figure>
currently the best-known bound for this problem. For several special metric spaces there are even tighter bounds known for this algorithm [11, 26, 55]. Very recently, Bubeck, Coester and Rabani [16] proved a lower bound of $\Omega(\log^2 k)$ on the randomized competitive ratio of the $k$-server problem, disproving a long-standing conjecture which suggested the existence of a randomized $O(\log k)$-competitive algorithm. For memoryless randomized algorithms, a lower bound of $k$ on the competitive ratio has been shown by Koutsoupias [34] and more general (weighted) variants have been investigated recently by Chiplunkar and Vishwanathan [20].

Different generalizations of the $k$-server problem have been considered. In the $k$-taxi problem, a request may relocate its server to another (known) point [18, 25]. Another line of research allows requests to ask for a specific set of servers [19, 24].

The optimal offline solution for the $k$-server problem can be computed efficiently via a reduction to minimum-cost flow problem [23], and recent efforts showed an improved running time by instead reducing to a shortest-path problem [48].

# 2 Algorithm and Roadmap for the Analysis

In this section we define the algorithm LAMBDADC and then give a high-level overview of our analyses as well as matching lower bounds. In the following, we denote a server's name as well as its position on the line by $s_i$, for $i \in \{1, 2, ..., k\}$. Our algorithm ensures that at any time $s_1 \le \dots \le s_k$.

## 2.1 The Algorithm LAMBDADC

The classical algorithm DOUBLECOVERAGE [23] for the $k$-server problem on the line is as follows. Upon a request, it moves a closest server on the left of the current request and a closest server on the right of the current request towards it with the same speed, and stops them as soon as the request has been served.

We generalize this algorithm and derive our algorithm LAMBDADC (Algorithm 1) by including the information about predicted servers as well as our trust into this advice in an intuitive way: if a request $r_t$ appears between two servers, the one closer to the predicted server $p_t$ moves towards the request with a higher speed than the other server. Notice that if $\lambda = 0$, LAMBDADC equals FTP, and if $\lambda = 1$, LAMBDADC equals DOUBLECOVERAGE. Using non-integral values for $\lambda$ gives an algorithm that interpolates between both.
**Input:** confidence parameter $\lambda \in [0, 1]$, request $r_t$, prediction $p_t$.

1. **if** $r_t < s_1$ or $r_t > s_k$ **then**

2. Move the closest server to $r_t$.

3. **else**

4. Find $i \in \{1, \dots, k-1\}$ such that $s_i \le r_t \le s_{i+1}$.

5. **if** $p_t \le i$ **then**

6. Move $s_i$ with speed 1 and $s_{i+1}$ with speed $\lambda$ towards $r_t$ until one of them reaches the request.

7. **else**

8. Move $s_i$ with speed $\lambda$ and $s_{i+1}$ with speed 1 towards $r_t$ until one of them reaches the request.

9. **end if**

10. **end if**

**Algorithm 1** LAMBDADC

## 2.2 Potential Function Analysis

The analysis of LAMBDADC builds on the powerful potential function method, as does the analysis of the classical DOUBLECOVERAGE [23].

Our potential analysis follows the well-known interleaving moves technique [13]. To compare two algorithms $\mathcal{A}$ and $\mathcal{B}$ in terms of competitiveness, we simulate both in parallel on some instance $I$. Then, we employ a potential function $\Phi$ that maps at every time $t$ the state of both algorithms (that is, the algorithms current configurations) to a value $\Phi_t \ge 0$, the potential at time $t$. We define $\Delta\Phi_t = \Phi_t - \Phi_{t-1}$. Let $\Delta B_t(I)$ and $\Delta A_t(I)$ denote the cost $\mathcal{A}$ and $\mathcal{B}$ incur for serving request $r_t$, respectively, and let $\mu > 0$. For every request $r_t$, we assume that first $\mathcal{B}$ serves the request, and then $\mathcal{A}$. If

(i) the move of $\mathcal{B}$ increases $\Phi$ by at most $\mu \cdot \Delta B_t(I)$, whereas

(ii) the move of $\mathcal{A}$ decreases $\Phi$ by at least $\Delta A_t(I)$,

a telescoping sum gives

$$ \Phi_n - \Phi_0 = \sum_{t=1}^{n} \Delta\Phi_t \le \sum_{t=1}^{n} (\mu \cdot \Delta B_t(I) - \Delta A_t(I)) = \mu \cdot \mathcal{B}(I) - \mathcal{A}(I). $$

Since $\Phi_n \ge 0$, we conclude $\mathcal{A}(I) \le \mu \cdot \mathcal{B}(I) + \Phi_0$. Note that if $\mathcal{B}$ is the optimal algorithm, $\mu$ is an upper bound on the competitive ratio of $\mathcal{A}$ since $\Phi_0$ only depends on the initial configuration $C_0$.

The potential functions we use to analyze LAMBDADC are inspired by the potential function in the analysis of DOUBLECOVERAGE [23]. They have the form $\Phi = \Psi + \Theta$, where $\Psi$ is the *matching part*, which sums the distances between the server positions of an algorithm and the reference algorithm (OPT, FTP), and $\Theta$ is the *spreadness part*, which sums the distances between an algorithms server positions. To incorporate the
more sophisticated server moves at different speeds of LAMBDADC, we introduce multiplicative coefficients to both parts. The main technical contribution lies in identifying the proper weights and performing the much more involved analysis. The potentials will be properly defined later.

## 2.3 Roadmap

For a fixed instance $I$, we denote the total cost of LAMBDADC by $ALG(I)$. The proof of the upper bounds of LAMBDADC (Theorem 1) is composed of the following two bounds, for any $\lambda \in [0, 1]$:

* the consistency bound $ALG(I) \le \alpha(\lambda, k) \cdot FTP(I) + c$ for some $c > 0$ and for every instance $I$ (Lemma 9), and

* the robustness bound $ALG(I) \le \beta(\lambda, k) \cdot OPT(I) + c$ for some $c > 0$ and for every instance $I$ (Lemma 16).

Then, using $FTP(I) = OPT(I) + \eta$, we can immediately derive Theorem 1.

For ease of exposition, we first consider the setting of 2 servers in Sect. 3 and prove the above bounds for this simpler case. We also show that in this setting LAMBDADC achieves an optimal consistency-robustness tradeoff among all memory-constrained algorithms, that is, a special case of Theorem 2. Then, in Sects. 4 and 5, we extend the techniques to the general setting and give complete proofs for Theorems 1 and 2 while maintaining the same structure as in the 2-server case. Finally, we prove learnability of our predictions in Sect. 6, and discuss the results of computational experiments in Sect. 7.

# 3 Full Analysis for Two Servers

## 3.1 Upper Bounds

We show the theoretical guarantees of LAMBDADC claimed in Theorem 1 restricted to two servers as they are given in the following theorem.

**Theorem 3** For any parameter $\lambda \in [0, 1]$, LAMBDADC has a competitive ratio of at most

$$ \min \left\{ (1 + \lambda) \left( 1 + \frac{\eta}{OPT} \right), 1 + \frac{1}{\lambda} \right\} $$

for the 2-server problem on the line. Thus, it is $(1 + \lambda)$-consistent and $(1 + 1/\lambda)$-robust.

We follow the two-step approach outlined in the previous section, where we first prove that $ALG \le (1 + \lambda) \cdot FTP + c$ (Lemma 4) and second prove that $ALG \le (1 + 1/\lambda) \cdot OPT + c$ (Lemma 5). Here, $c \ge 0$ is a constant that only depends on the initial configuration.
**Lemma 4** For any instance *I* and $\lambda \in [0, 1]$, there is some $c \ge 0$ that only depends on the initial configuration such that $\mathrm{ALG}(I) \le (1 + \lambda) \cdot \mathrm{FTP}(I) + c$.

**Proof** Let *I* be an arbitrary instance and let servers start at positions $s_1^0$ and $s_2^0$. If $\lambda = 0$, LAMBDA DC corresponds to FTP, hence $\mathrm{ALG}(I) = \mathrm{FTP}(I)$. Now assume that $\lambda > 0$. Let $s_1$, $s_2$ be LAMBDA DC ’s servers and $x'_1$, $x'_2$ be FTP ’s servers. By the assumption that the prediction moves no server past another, we always have $x'_1 \le x'_2$. We simulate both algorithms in parallel for instance *I*. At every time *t*, we map the configurations of both algorithms to a non-negative value using the potential function

$$ \Phi = \underbrace{\frac{1 + \lambda}{\lambda} (|s_1 - x'_1| + |s_2 - x'_2|)}_{\Psi \text{ (matching part)}} + \underbrace{|s_1 - s_2|}_{\Theta \text{ (spreadness part)}} . $$

Suppose that a request arrives. First, FTP serves the request. Assume that $x'_1$ moves and incurs cost $\Delta \mathrm{FTP}$. Since LAMBDA DC remains in its previous configuration, $|x'_1 - s_1|$ increases by at most $\Delta \mathrm{FTP}$, and $\Phi$ increases by at most $(1 + \lambda)/\lambda \cdot \Delta \mathrm{FTP}$. Second, LAMBDA DC moves and incurs a total cost of $\Delta \mathrm{ALG}$. We assume by scaling the instance that the algorithm serves the request after exactly one time unit. We distinguish whether the request is between the algorithm’s servers or not, and prove in each case that $\Phi$ decreases by at least $1/\lambda \cdot \Delta \mathrm{ALG}$.

(a) Suppose the request is not between the servers $s_1$ and $s_2$; say, it is to the left of $s_1$. Then, LAMBDA DC moves only $s_1$ by distance 1, and $\Delta \mathrm{ALG} = 1$. Either $x'_1$ or $x'_2$ covers the request, meaning that $x'_1$ is at or to the left of the request. Hence, moving $s_1$ decreases $\Psi$ by $(1 + \lambda)/\lambda$ while it increases $\Theta$ by 1. Thus,

$$ \Delta\Phi \le -\frac{1 + \lambda}{\lambda} + 1 = -\frac{1}{\lambda} = -\frac{1}{\lambda} \cdot \Delta\mathrm{ALG}. $$

(b) Suppose the request is between $s_1$ and $s_2$, and suppose that $s_1$ is predicted. Then, LAMBDA DC moves $s_1$ by distance 1 to the right and $s_2$ by distance $\lambda$ to the left. Hence, $\Delta \mathrm{ALG} = 1 + \lambda$. Since $s_1$ is predicted, $x'_1$ already covers the request. Thus, moving $s_1$ decreases $\Psi$ by $(1 + \lambda)/\lambda$, while moving $s_2$ increases $\Psi$ by at most $(1 + \lambda)/\lambda \cdot \lambda$. Also, $\Theta$ decreases by $1 + \lambda$. We conclude that

$$ \Delta\Phi \le \frac{1 + \lambda}{\lambda}(-1 + \lambda) - (1 + \lambda) = -\frac{1}{\lambda}(1 + \lambda) = -\frac{1}{\lambda} \cdot \Delta\mathrm{ALG}. $$

Summing over all rounds, we obtain $\mathrm{ALG}(I) \le (1 + \lambda)\mathrm{FTP}(I) + \lambda|s_1^0 - s_2^0|$. $\square$

Next, we give a robustness guarantee for LAMBDA DC ’s performance independently of the prediction quality.

**Lemma 5** For any instance *I* and $\lambda \in (0, 1]$, there is some $c \ge 0$ that only depends on the initial configuration such that $\mathrm{ALG}(I) \le (1 + 1/\lambda) \cdot \mathrm{OPT}(I) + c$.
The proof of this claim is similar to the proof of Lemma 4 with the crucial difference that we compare our algorithm to the optimal solution, hence the multiplicative factor is larger.

**Proof** Let $I$ be an arbitrary instance and let $\lambda \in (0, 1]$. Let $s_1, s_2$ be LAMBDADC's servers and $x_1, x_2$ the servers of an optimal algorithm. We define

$$ \Phi = \underbrace{(1 + \lambda) (|s_1 - x_1| + |s_2 - x_2|)}_{\Psi} + \underbrace{|s_1 - s_2|}_{\Theta}. $$

Upon arrival of a request, first the optimal algorithm moves and $\Phi$ increases by at most $(1 + \lambda) \cdot \Delta \text{OPT}$. Second, LAMBDADC moves. By scaling the instance, we assume that the request is served after exactly one time unit. We distinguish whether the request is between the algorithm's servers or not, and show that in each case $\Phi$ decreases by at least $\lambda \cdot \Delta \text{ALG}$.

(a) Let the request be not between the servers, say on the left of $s_1$. Since $x_1$ or $x_2$ covers the request, $x_1$ is at or to the left of the request. Hence, moving $s_1$ decreases $\Psi$ by $1 + \lambda$ while it increases $\Theta$ by 1. Thus,

$$ \Delta\Phi \le -(1 + \lambda) + 1 = -\lambda = -\lambda \cdot \Delta\text{ALG}. $$

(b) Let the request be between $s_1$ and $s_2$, and suppose that $s_1$ is predicted. The request is covered by $x_1$ or $x_2$. In the worst case ($x_2$ covers the request), moving $s_1$ towards the request increases $\Psi$ by at most $1 + \lambda$, while $s_2$ decreases $\Psi$ only by $(1 + \lambda)\lambda$. Also, $\Theta$ decreases by $1 + \lambda$. Put together,

$$ \Delta\Phi \le (1 + \lambda)(1 - \lambda) - (1 + \lambda) = -\lambda(1 + \lambda) = -\lambda \cdot \Delta\text{ALG}. \square $$

## 3.2 Pareto-Optimality of LAMBDADC

We now show that LAMBDADC is optimal for two servers, in the sense that no memory-constrained algorithm can achieve a better robustness-consistency tradeoff. As we target memory-constrained algorithms, at any time, we can use force requests, cf., Sect. refsec:intro, to enforce the algorithm to place its servers at prescribed locations. We first state the following variant of Theorem 2 for the special case of two servers.

**Theorem 6** Let $\mathcal{A}$ be a learning-augmented memory-constrained algorithm for the 2-server problem on the line and let $\lambda \in (0, 1]$. If $\mathcal{A}$ is $(1 + \lambda)$-consistent, it has a robustness ratio of at least $1 + 1/\lambda$.

**Proof** Let $\lambda \in (0, 1]$ and $\mathcal{A}$ be a $(1 + \lambda)$-consistent, memory-constrained algorithm for the 2-server problem on the line. This means for every instance $I$, $\mathcal{A}(I) \le (1 + \lambda) \cdot \text{OPT}(I) + c$ if $\eta = 0$, where $c$ depends on the initial
configuration. Let $x, y$, and $z$ be consecutive points on the line at position $-1, 0$ and $L \ge 1 + 1/\lambda$, and $(x, y)$ the algorithm's initial configuration. Recall that a memory-constrained algorithm does not cross servers. Thus, the server that is initially on $x$ is at every time to the left of the other server.

Consider the instance $I^\infty$ that is composed of a force to $(x, z)$, followed by arbitrarily many alternating requests at $y$ and $x$. Clearly, an optimal solution for instance $I^\infty$ is to move the right server to $z$ and then immediately back to $y$ with a total cost of $2L$.

Assume that $\mathcal{A}$ gets this optimal solution as prediction. $\mathcal{A}$ moves one server to $z$ for the first request. Since the consistency implies that $\mathcal{A}(I^\infty) \le (1+\lambda)\text{OPT} + c$, at some point in time $\mathcal{A}$ has to move the right server to $y$. Denote the instance that ends at this point in time by $I$. Note that $\mathcal{A}(I^\infty) \ge \mathcal{A}(I)$. Let $n_L$ denote the number of times in instance $I$ where the left server moves from $x$ to $y$ and back to $x$ with a total cost of $2$. Since the right server pays at least $L$ for moving from $z$ to $y$, we conclude $\mathcal{A}(I) \ge 2n_L + 2L$. The consistency of $\mathcal{A}$ leads to $2n_L + 2L \le (1+\lambda)2L + c$, which means $n_L \le \lambda L + c/2$.

We now construct another instance $I^\omega$ by concatenating $\omega$ copies of instance $I$, each starting by the force to $(x, z)$. We call such a copy an *iteration*, and in each iteration we use the same predictions as in instance $I$. Algorithm $\mathcal{A}$ has to pay at least $L$ for the force, as the right server was previously on $y$, and then $\mathcal{A}$ follows the same behavior as in $I$ in each iteration. So $\mathcal{A}(I^\omega) \ge \omega \cdot (2n_L + 2L)$. Another solution for instance $I^\omega$ is to move the right server to $z$ in the beginning with cost $L$ and leave it there, while the left server alternates between $x$ and $y$. Hence, $\text{OPT}(I^\omega) \le L + \omega \cdot 2(n_L + 1)$. Indeed, $y$ is requested $n_L + 1$ times per iteration: $n_L$ where $\mathcal{A}$ uses the left server and one where it uses the right server. The ratio is then

$$ \frac{\mathcal{A}(I^\omega)}{\text{OPT}(I^\omega)} \ge \frac{\omega \cdot (2n_L + 2L)}{L + \omega \cdot 2(n_L + 1)} \xrightarrow{\omega \to \infty} \frac{2n_L + 2L}{2(n_L + 1)} = 1 + \frac{L-1}{n_L + 1} \\ \ge 1 + \frac{L-1}{\lambda L + \frac{c}{2} + 1} \xrightarrow{L \to \infty} 1 + \frac{1}{\lambda}, $$

which implies the lemma. $\square$

## 4 An Upper Bound for $k$ Servers

To prove Theorem 1 for $k > 2$, we again follow the previously outlined approach. The key contribution lies in designing appropriate potential functions that capture the server movements at different speeds. This takes substantially more technical care than in the 2-server case (Theorem 3) but builds on similar ideas. At the end of this section, we show that the bounds given in Theorem 1 are tight.
## 4.1 The Consistency Bound

In the first step of the analysis, we compare the performance of LAMBDADC and FTP. Let $I$ be an arbitrary instance. Recall that

$$ \alpha(\lambda, k) = \begin{cases} 1 + 2\lambda + 2\lambda^2 + \dots + 2\lambda^{(k-1)/2} & \text{if } k \text{ is odd, and} \\ 1 + 2\lambda + 2\lambda^2 + \dots + 2\lambda^{k/2-1} + \lambda^{k/2} & \text{if } k \text{ is even.} \end{cases} $$

Note that $\lambda = 0$ implies ALG($I$) = FTP($I$), so we now fix a $\lambda \in (0, 1]$, and write $\alpha(k)$ for $\alpha(\lambda, k)$.

We define a new potential function $\Phi$ as follows. Let $s_1, \dots, s_k$ be the servers of LAMBDADC and let $x'_1, \dots, x'_k$ be the servers of FTP. By the assumption that the prediction moves no server past another, we always have $x'_1 \le \dots \le x'_k$. For $1 \le i < j \le k$ and $\ell = \min\{j - i, k - (j - i)\} - 1$ we define $\delta_{ij} = \lambda^\ell$. Then,

$$ \Phi = \underbrace{\frac{\alpha(k)}{\lambda} \cdot \sum_{i=1}^{k} |s_i - x'_i|}_{\Psi} + \underbrace{\sum_{i=1}^{k} \sum_{j=i+1}^{k} \delta_{ij} |s_i - s_j|}_{\Theta} $$

Intuitively, the leading coefficient of $\Psi$ comes from the targeted competitive ratio. Then, in $\Theta$, the coefficient in front of each term depends on the number of interleaving servers. Following the idea of Lemma 17, when LAMBDADC moves a server by a distance of 1, its neighbor moves by a distance of $\lambda$. Hence, correcting the position of this neighbor means that the next server moves by a distance $\lambda^2$. Therefore, this geometric decrease in the consequences of a movement also appears in the expression of $\Theta$.

We start with rewriting $\alpha(k)$ as a recursive function.

**Proposition 7** For every $k > 3$, we have $\frac{\alpha(k)}{\lambda} = \alpha(k - 2) + \frac{1}{\lambda} + 1$.

**Proof** We prove this statement depending on the parity of $k$. If $k$ is odd, $k - 2$ is also odd. By definition of $\alpha(k)$,

$$ 1 + \frac{1}{\lambda} + \alpha(k-2) = \frac{1}{\lambda} + 2 + 2 \sum_{i=1}^{(k-3)/2} \lambda^i = \frac{1}{\lambda} + 2 \sum_{i=1}^{(k-1)/2} \lambda^{i-1} = \frac{\alpha(k)}{\lambda}. $$

If $k$ is even, $k - 2$ is also even, and we conclude

$$ \begin{aligned} 1 + \frac{1}{\lambda} + \alpha(k-2) &= \frac{1}{\lambda} + 2 + 2 \sum_{i=1}^{(k-2)/2-1} \lambda^i + \lambda^{(k-2)/2} \\ &= \frac{1}{\lambda} + 2 \sum_{i=1}^{k/2-1} \lambda^{i-1} + \lambda^{(k-2)/2} = \frac{\alpha(k)}{\lambda}. \square \end{aligned} $$
The analysis of LAMBDADC requires evaluating the evolution of $\Phi$ after each request. The following lemma characterizes how a move of LAMBDADC influences $\Theta$.

**Lemma 8** Let $i \le \lfloor k/2 \rfloor$. If $s_i$ moves from $p$ to $p-x$ for some $x \in \mathbb{R}$ without over-taking other servers, $\Theta$ changes by

$$x \cdot \left( 1 + \alpha(k-2) - 2 \sum_{j=0}^{i-2} \lambda^j \right).$$

*Proof* Without loss of generality, we assume by scaling that $x = 1$. That is, the server $s_i$ moves one unit to the left. Consider servers $s_j$, $s_{j'}$ such that $j' + \ell = i = j - \ell$ for some $1 \le \ell \le i - 1$. Note that before and after $s_i$'s moves, $s_j \le s_i \le s_{j'}$ holds. Thus, the distance between $s_i$ and $s_j$ decreases by one, and the distance between $s_i$ and $s_{j'}$ increases by one. Since $\delta_{ij'} = \delta_{ij}$, this concludes that the changes to the terms $\delta_{ij}|s_i - s_j|$ and $\delta_{ij'}|s_i - s_{j'}|$ of $\Theta$ cancel out. Hence, as $i \le \lfloor k/2 \rfloor$, the change of $\Theta$ due to the move (of distance one) of $s_i$ is equal to $\sum_{j=2i}^k \delta_{ij}$. Continuing with this term, we prove the statement depending on the parity of $k$.

(i) If $k$ is odd, $k - 2i + 1$ is even. Thus, there are two consecutive values of $j$ where the minimum in the definition of $\delta_{ij}$ is achieved by both terms. By definition,

$$\begin{aligned} \sum_{j=2i}^{k} \delta_{ij} &= \sum_{j=2i}^{k} \lambda^{\min\{j-i, k-(j-i)\}-1} = 2 \sum_{j=2i}^{(k-1)/2+i} \lambda^{j-i-1} = 2 \sum_{j=i-1}^{(k-1)/2-1} \lambda^j \\ &= 2 + 2 \sum_{j=1}^{(k-3)/2} \lambda^j - 2 \sum_{j=0}^{i-2} \lambda^j = 1 + \alpha(k-2) - 2 \sum_{j=0}^{i-2} \lambda^j. \end{aligned}$$

(ii) If $k$ is even, $k - 2i + 1$ is odd, and there is a single $j$ value where the minimum in the definition of $\delta_{ij}$ is achieved by both terms. Hence,

$$\begin{aligned} \sum_{j=2i}^{k} \lambda^{\min\{j-i, k-(j-i)\}-1} &= 2 \sum_{j=2i}^{k/2-1+i} \lambda^{j-i-1} + \lambda^{k/2-1} = 2 \sum_{j=i-1}^{k/2-2} \lambda^j + \lambda^{k/2-1} \\ &= 2 + 2 \sum_{j=1}^{k/2-2} \lambda^j + \lambda^{k/2-1} - 2 \sum_{j=0}^{i-2} \lambda^j \\ &= 1 + \alpha(k-2) - 2 \sum_{j=0}^{i-2} \lambda^j. \square \end{aligned}$$

Now, we are ready to analyze the performance of LAMBDADC with respect to FTP.
**Lemma 9** For every instance I and $\lambda \in [0, 1]$, there is some $c > 0$ that only depends on the initial configuration such that $\mathrm{ALG}(I) \le \alpha(\lambda, k) \cdot \mathrm{FTP}(I) + c$.

*Proof* Suppose that a request appears. First FTP moves some server $x'_i$ towards the request, and the distance to $s_i$ increases by at most $\Delta \mathrm{FTP}$. Since this move only affects $\Psi$, $\Delta\Phi \le \alpha(k)/\lambda \cdot \Delta \mathrm{FTP}$. Second LAMBDA DC moves. We distinguish whether the request is between two servers or not, and assert for both cases $\Delta\Phi \le -1/\lambda \cdot \Delta \mathrm{ALG}$.

(a) Without loss of generality, let the request be located on the left of $s_1$. Thus, $s_1$ moves towards it and incurs cost $\Delta \mathrm{ALG}$. The fact that some server $x'_j$ must already be at the requested position combined with Lemma 8 implies that

$$ \Delta\Phi \le -\frac{\alpha(k)}{\lambda}\Delta\mathrm{ALG} + \left(1 + \alpha(k-2) - 2\sum_{j=0}^{1-2}\lambda^j\right)\Delta\mathrm{ALG}. $$

Rearranging and using Proposition 7 gives the claimed bound, that is

$$ \left(-\alpha(k-2) - \frac{1}{\lambda} - 1 + 1 + \alpha(k-2)\right) \Delta\mathrm{ALG} = -\frac{1}{\lambda}\Delta\mathrm{ALG}. $$

(b) Let the request be between $s_i$ and $s_{i+1}$. Assume without loss of generality that FTP serves it with $x'_j$ and $j \le i$. For ease of exposition, we assume that $s_i$ travels distance 1 and $s_{i+1}$ distance $\lambda$. Hence, $\Delta \mathrm{ALG} = 1 + \lambda$. Since $j \le i$, we know that $x'_i$ must be located on the right of $x'_j$. Hence, the distance between $s_i$ and $x'_i$ decreases by 1, but the distance between $s_{i+1}$ and $x'_{i+1}$ increases by at most $\lambda$. Thus, $\Delta\Psi \le \alpha(k)/\lambda \cdot (\lambda - 1)$. The change of $\Theta$ is clearly bounded from above by the case where $s_i$ moves distance $\lambda$ and $s_{i+1}$ moves distance 1 for $i + 1 \le \lfloor k/2 \rfloor$. Combining Lemma 8 for both servers gives

$$ \begin{aligned} \Delta\Theta &= 1 + \alpha(k-2) - 2\sum_{j=0}^{i-1}\lambda^j - \lambda \left(1 + \alpha(k-2) - 2\sum_{j=0}^{i-2}\lambda^j\right) \\ &= -1 - \lambda + \alpha(k-2) - \lambda\alpha(k-2). \end{aligned} $$

Using this and Proposition 7, we can bound the increase of the potential by

$$ \begin{aligned} \Delta\Phi &\le \frac{\alpha(k)}{\lambda}(\lambda-1) - 1 - \lambda + \alpha(k-2) - \lambda\alpha(k-2) \\ &= -\frac{\alpha(k)}{\lambda} + \alpha(k-2) = -1 - \frac{1}{\lambda} = -\frac{1}{\lambda}\Delta\mathrm{ALG}. \square \end{aligned} $$
## 4.2 The Robustness Bound

Proving the general upper bound on the robustness ratio is much more intricate than in the 2-server case and in the consistency proof. Again, our key ingredient is a carefully chosen potential function $\Phi$. We generalize the function used for the consistency bound even further by refining the weights, specifically, adding server-dependent weights to the term $\Psi$ measuring the distance between the positions of the algorithm’s servers and the optimal servers.

### 4.2.1 Definition of the Potential Function

Fix a $\lambda \in (0, 1]$ and $k$. We write $\beta$ for $\beta(\lambda, k) = \sum_{i=0}^{k-1} \lambda^{-i}$. Let $s_1, \dots, s_k$ be the servers of LAMBDADC and let $x_1, \dots, x_k$ be the servers of an optimal solution. The potential function $\Phi$ is defined as follows:

$$ \Phi = \beta\gamma \underbrace{\left(\sum_{i=1}^{k} \omega_i |s_i - x_i|\right)}_{\Psi} + \underbrace{\sum_{i<j} \delta_{ij} |s_i - s_j|}_{\Theta} $$

We specify the weights in this function as follows. For a pair of servers $s_i, s_j$ with $1 \le i < j \le k$, let $\ell = \min\{j - i, k - (j - i)\} - 1$ and $\delta_{ij} = (\lambda^\ell + \lambda^{k-2-\ell})/(1 + \lambda^{k-2})$.

The intuition of the weights in the spreadness part $\Theta$ is the same as in the consistency potential function above. However, the new weights $\omega_i$ in the matching part $\Psi$ (defined below) require the more complex weights $\delta_{ij}$ compared to the simpler $\lambda^\ell$ weights.

Further, we define $d_{\lceil k/2 \rceil} = 0$ if $k$ is odd, and for all $1 \le i \le \lceil k/2 \rceil$ let

$$ d_i = d_{k+1-i} = \frac{2}{1 + \lambda^{k-2}} \sum_{\ell=i-1}^{k-1-i} \lambda^{\ell}. $$

Let $\gamma = d_1/(\beta - 1)$, $\omega_1 = \omega_k = 1$, and for $2 \le i \le \lceil k/2 \rceil$ we define the server-individual weights if $i$ is even

$$ \omega_i = \omega_{k+1-i} = \frac{2\lambda \sum_{j=1}^{i/2-1} d_{2j} - 2 \sum_{j=1}^{i/2-1} d_{2j+1} + \lambda d_i + (2+\lambda)\gamma}{\beta\gamma\lambda}, \quad (1) $$

and if $i$ is odd

$$ \omega_i = \omega_{k+1-i} = \frac{2\lambda \sum_{j=1}^{(i-1)/2} d_{2j} - 2 \sum_{j=1}^{(i-3)/2} d_{2j+1} - d_i + \gamma}{\beta\gamma}. \quad (2) $$
This potential function is carefully tailored to the desired analysis. In the following we give some intuition. We choose the scaling parameter $\gamma$ such that the decrease of $\Phi$ exactly matches the required lower bound for the case where the request is outside the convex hull of LAMBDAADC's servers. The remaining cases are split among the possible locations where a request can appear between two servers of LAMBDAADC, and we show in each case that $\Phi$ decreases enough. The definition of the $\omega$ values ensures that a wrong prediction gives a tight bound on the decrease of $\Phi$ for LAMBDAADC's move, while a correct prediction still guarantees a loose bound.

### 4.2.2 Properties of the Potential Function

Before showing connections between the potential, the optimal solution and LAMBDAADC, we state some properties of the potential function $\Phi$. These help us to describe parts of the potential differently, which will be useful later.

We start with several algebraic transformations of $\gamma$. Their technical proofs are deferred to the appendix.

**Lemma 10** The following statements are true:

(i) $\gamma = 2\lambda^{k-1}/(1 + \lambda^{k-2})$.

(ii) For all $1 \le i \le \lfloor k/2 \rfloor$, it holds $(1 + \lambda)\gamma = \lambda^{i+1}d_i - \lambda^i d_{i+1}$.

(iii) If $k$ is even, it holds $\gamma = \lambda d_1 + (1 + \lambda) \sum_{j=2}^{k/2} (-1)^{j-1} d_j$.

We continue with two more involved observations about the weights chosen for our potential function. The first observation is important for all cases where a request appears between two servers. Recall the definition of $\Phi$. If $s_i$ moves with speed $\lambda$ and $s_{i+1}$ with speed 1, the changes to $\Psi$ (increase or decrease) are scaled by $\beta\gamma\lambda\omega_i$ regarding $s_i$ and $\beta\gamma\omega_{i+1}$ regarding $s_{i+1}$. If $i$ is even, we can easily use the definition of $\omega$, since the denominators cancel. However, if $i$ is odd, we use the following alternative representation of the $\omega$-weights.

**Lemma 11** For even $2 \le i \le \lfloor k/2 \rfloor$, $\omega_i$ is equal to

$$ \frac{1}{\beta\gamma} \left( 2\lambda \sum_{j=1}^{i/2} d_{2j-1} - 2 \sum_{j=1}^{i/2-1} d_{2j} - d_i - \gamma \right). $$

**Proof** We first note that for every $1 \le j \le \lfloor k/2 \rfloor - 1$, applying Lemma 10(ii) with $j$ and $j+1$ yields

$$ \lambda d_j - d_{j+1} = \frac{1 + \lambda}{\lambda^j} \gamma = \lambda^2 d_{j+1} - \lambda d_{j+2}. \quad (3) $$

We now prove the statement by induction. As induction base, we first prove the claim for $i = 2$. Indeed,
$$ \omega_2 = \frac{\lambda d_2 + (2 + \lambda)\gamma}{\beta\gamma\lambda} = \frac{d_2 + (2 + \lambda)\gamma/\lambda}{\beta\gamma} = \frac{2\lambda d_1 - d_2 - \gamma}{\beta\gamma}. $$

Note that the last equality derives from Lemma 10(ii). Now assume that $i > 2$ is even. The induction hypothesis for $i - 2$ yields in this case

$$ \beta\gamma\lambda \cdot \omega_{i-2} = 2\lambda^2 \sum_{j=1}^{i/2-1} d_{2j-1} - 2\lambda \sum_{j=1}^{i/2-2} d_{2j} - \lambda d_{i-2} - \lambda\gamma. \quad (4) $$

We want to prove that $\beta\gamma\lambda \cdot \omega_i$ is equal to

$$ 2\lambda^2 \sum_{j=1}^{i/2} d_{2j-1} - 2\lambda \sum_{j=1}^{i/2-1} d_{2j} - \lambda d_i - \lambda\gamma, $$

which can be rearranged to

$$ 2\lambda^2 \sum_{j=1}^{i/2-1} d_{2j-1} - 2\lambda \sum_{j=1}^{i/2-2} d_{2j} - \lambda d_{i-2} - \lambda\gamma - \lambda d_i - \lambda d_{i-2} + 2\lambda^2 d_{i-1}. $$

Replacing the right side of (4) in the above expression yields

$$ \beta\gamma\lambda \cdot \omega_{i-2} - \lambda d_i - \lambda d_{i-2} + 2\lambda^2 d_{i-1}. $$

Since (3) gives $2(1 + \lambda^2)d_{i-1} = 2\lambda(d_{i-2} + d_i)$, and by the definition (1) of $\omega_{i-2}$, this can be rewritten to

$$ \begin{aligned} & 2\lambda \sum_{j=1}^{i/2-2} d_{2j} - 2 \sum_{j=1}^{i/2-2} d_{2j+1} + \lambda d_{i-2} + (2 + \lambda)\gamma - 2d_{i-1} + \lambda d_{i-2} + \lambda d_i \\ & = 2\lambda \sum_{j=1}^{i/2-1} d_{2j} - 2 \sum_{j=1}^{i/2-1} d_{2j+1} + (2 + \lambda)\gamma + \lambda d_i, \end{aligned} $$

which is indeed equal to $\beta\gamma\lambda \cdot \omega_i$ by definition (1).

<figure><img src="image_6.png" /></figure>

The proof of the odd case is similar and thus deferred to the appendix:

**Lemma 12** For odd $2 \le i \le \lfloor k/2 \rfloor$, $\omega_i$ is equal to

$$ \frac{1}{\beta\gamma\lambda} \left( 2\lambda \sum_{j=1}^{(i-1)/2} d_{2j-1} - 2 \sum_{j=1}^{(i-1)/2} d_{2j} + \lambda d_i + \lambda\gamma \right). $$
The second observation is an upper and a lower bound of the $\omega$-weights regardless of the corresponding server. The lower bound is necessary to show that $\Phi \ge 0$, while we use the upper bound to give an easy upper bound on the increase of the potential when the optimal solution moves, independently of its chosen server.

**Lemma 13** For even $1 \le i \le k$ holds that $0 \le \omega_i \le 1$.

*Proof* By definition, $\omega_k = 1$. We now show this property for even $2 \le i \le k - 1$. Assume that $i$ is even. By definition, the numerator of $\omega_i$ is equal to

$$2\lambda \sum_{j=1}^{i/2-1} d_{2j} - 2 \sum_{j=1}^{i/2-1} d_{2j+1} + \lambda d_i + (2 + \lambda)\gamma.$$

Using the definition of $d_i$ and Lemma 10(i) gives

$$\begin{aligned} & \frac{2}{1 + \lambda^{k-2}} \left( \lambda \sum_{j=1}^{i/2-1} \sum_{\ell=2j-1}^{k-1-2j} 2\lambda^{\ell} - \sum_{j=1}^{i/2-1} \sum_{\ell=2j}^{k-2-2j} 2\lambda^{\ell} + \lambda \sum_{\ell=i-1}^{k-1-i} \lambda^{\ell} \right) + (2 + \lambda)\gamma \\ &= \frac{2}{1 + \lambda^{k-2}} \left( \sum_{j=1}^{i/2-1} 2(\lambda^{k-2j} + \lambda^{k-1-2j}) + \sum_{\ell=i}^{k-i} \lambda^{\ell} \right) + (2 + \lambda)\gamma \\ &= \frac{2}{1 + \lambda^{k-2}} \left( \sum_{\ell=k-i+1}^{k-2} 2\lambda^{\ell} + \sum_{\ell=i}^{k-i} \lambda^{\ell} \right) + (2 + \lambda)\gamma \\ &= \frac{2}{1 + \lambda^{k-2}} \left( \sum_{\ell=k-i+1}^{k-1} 2\lambda^{\ell} + \sum_{\ell=i}^{k-i} \lambda^{\ell} \right) + \lambda\gamma \end{aligned}$$

Since $\beta\gamma\lambda = \lambda\gamma + \lambda d_1 \ge 0$, we conclude that $\omega_i \ge 0$. Further, using the fact that $\sum_{\ell=k-i+1}^{k-1} \lambda^\ell \le \sum_{\ell=1}^{i-1} \lambda^\ell$ yields

$$\frac{2}{1 + \lambda^{k-2}} \left( \sum_{\ell=k-i+1}^{k-1} 2\lambda^{\ell} + \sum_{\ell=i}^{k-i} \lambda^{\ell} \right) + \lambda\gamma \le \frac{2}{1 + \lambda^{k-2}} \sum_{\ell=1}^{k-1} \lambda^{\ell} + \lambda\gamma = \lambda d_1 + \lambda\gamma,$$

and we conclude that $\omega_i \le 1$.

The proof of the odd case is similar and thus deferred to the appendix:

**Lemma 14** For odd $1 \le i \le k$ holds that $0 \le \omega_i \le 1$.

### 4.2.3 Proof of the Robustness Bound

We first observe that the values $d_1, \dots, d_k$ correlate with the change of $\Theta$ when LAMBDA DC moves a server. This result is analogous to Lemma 8 in the consistency bound.
**Lemma 15** Let $i \le \lfloor k/2 \rfloor$. If server $s_i$ moves from $p$ to $p-x$ for some $x \in \mathbb{R}$, $\Theta$ changes by $x \cdot d_i$.

**Proof** Without loss of generality, we assume by scaling that $x = 1$. That is, the server $s_i$ moves one unit to the left. Consider servers $s_j, s_{j'}$ such that $j' + \ell = i = j - \ell$ for some $1 \le \ell \le i - 1$. Note that before and after $s_i$'s move holds $s_j \le s_i \le s_{j'}$. Thus, the distance between $s_i$ and $s_j$ decreases by one, and the distance between $s_i$ and $s_{j'}$ increases by one. Since $\delta_{ij'} = \delta_{ij}$, this concludes that the changes to the terms $\delta_{ij}|s_i - s_j|$ and $\delta_{ij'}|s_i - s_{j'}|$ of $\Theta$ cancel out. Hence, as $i \le \lfloor k/2 \rfloor$, it suffices to consider the distances of $s_i$ to servers $s_j$ with $j \ge 2i$. Therefore,

$$ \Delta\Theta = \sum_{j=2i}^{k} \delta_{ij} = \begin{cases} \sum_{\ell=i-1}^{k/2-2} 2\zeta_{\ell} + \zeta_{k/2-1} & \text{if } k \text{ is even, and} \\ \sum_{\ell=i-1}^{(k-3)/2} 2\zeta_{\ell} & \text{if } k \text{ is odd.} \end{cases} $$

The definition of $\zeta_\ell$ implies that this is indeed equal to $d_i$. $\square$

<figure><img src="image_7.png" /></figure>

We finally prove the robustness bound of LAMBDADC by exhaustively reviewing all possible moves and bounding the corresponding changes of $\Phi$.

**Lemma 16** For any instance I and $\lambda \in (0, 1]$, there is some $c \ge 0$ that only depends on the initial configuration such that $\mathrm{ALG}(I) \le \beta(\lambda, k) \cdot \mathrm{OPT}(I) + c$.

**Proof** Note that Lemmas 13 and 14 imply $\Phi \ge 0$. Suppose that a request arrives. First, the optimal solution increases due to Lemmas 13 and 14 the potential by at most $\beta\gamma\Delta\mathrm{OPT}$, while LAMBDADC remains in its previous configuration. Second, LAMBDADC moves. In the remaining proof, we show that the potential decreases by at least $\gamma\Delta\mathrm{ALG}$, which proves the lemma. To this end, we look at the following set of exhaustive cases that occur when LAMBDADC makes its move. We assume without loss of generality by scaling that in each case the fast server moves distance 1 and the slow server (if present) distance $\lambda$.

(a) Let the request without loss of generality be on the left of $s_1$. Hence, $\Delta\mathrm{ALG} = 1$, and $\Theta$ increases by $d_1$ due to Lemma 15. Recall that $\omega_1 = 1$. Since $x_1$ cannot be on the right side of the request, the potential changes by

$$ \Delta\Phi = -\beta\gamma + d_1 = -(d_1 - \gamma) + d_1 = -\gamma\Delta\mathrm{ALG}. $$

The remaining cases tackle situations where the request is located between the two servers $s_i$ and $s_{i+1}$. Without loss of generality we only look at those cases where $i \le \lfloor k/2 \rfloor$, since the others hold by the symmetry of the line and by the symmetry of $\Phi$.

(b) Let $1 \le i \le \lfloor k/2 \rfloor - 1$ and suppose that $s_i$ is predicted while the optimal solution serves the request with $x_j$ for some $j > i$. Note that $\Delta\mathrm{ALG} = 1 + \lambda$. The change of $\Phi$ is at most
$$ \Delta\Phi \leq \beta\gamma(\omega_i - \lambda\omega_{i+1}) - d_i + \lambda d_{i+1}. $$

By using (2) if i is odd, and Lemma 11 if i is even, this is equal to

$$ d_i - \lambda d_{i+1} - (1 + \lambda)\gamma - d_i + \lambda d_{i+1} = -\gamma(1 + \lambda) = -\gamma\Delta\text{ALG}. $$

(c) Let $1 \le i \le \lceil k/2 \rceil - 1$ and suppose that $s_{i+1}$ is predicted while the optimal solution serves the request with $x_j$ for some $j \le i$. The change of $\Phi$ is at most

$$ \Delta\Phi \leq \beta\gamma(\omega_{i+1} - \lambda\omega_i) - \lambda d_i + d_{i+1}. $$

By using (1) if i is even and Lemma 12 if i is odd, this is equal to

$$ \lambda d_i - d_{i+1} - (1 + \lambda)\gamma - \lambda d_i + d_{i+1} = -\gamma(1 + \lambda) = -\gamma\Delta\text{ALG}. $$

(d) Let $1 \le i \le \lceil k/2 \rceil - 1$ and suppose that $s_i$ is predicted while the optimal solution serves the request with $x_j$ for some $j \le i$. The change of $\Phi$ is at most

$$ \Delta\Phi \leq \beta\gamma(\lambda\omega_{i+1} - \omega_i) - d_i + \lambda d_{i+1}. $$

By using (2) if i is odd and Lemma 11 if i is even, this is equal to

$$ \begin{aligned} & -d_i + \lambda d_{i+1} + (1 + \lambda)\gamma - d_i + \lambda d_{i+1} \\ &= -\gamma(1 + \lambda) + 2(\lambda d_{i+1} - d_i + (1 + \lambda)\gamma) \\ &= -\gamma(1 + \lambda) + 2(\lambda d_{i+1} + \lambda^2 d_i - \lambda^2 d_i - d_i + (1 + \lambda)\gamma). \end{aligned} $$

Applying Lemma 10(ii) yields

$$ \begin{aligned} & -\gamma(1 + \lambda) + 2 \left( (\lambda^2 - 1)d_i - (1 + \lambda) \frac{\gamma}{\lambda^{i-1}} + (1 + \lambda)\gamma \right) \\ & \leq -\gamma(1 + \lambda) = -\gamma\Delta\text{ALG}. \end{aligned} $$

(e) Let $1 \le i \le \lceil k/2 \rceil - 1$ and suppose that $s_{i+1}$ is predicted while the optimal solution serves the request with $x_j$ for some $j > i$. The change of $\Phi$ is at most

$$ \Delta\Phi \leq \beta\gamma(\lambda\omega_i - \omega_{i+1}) - \lambda d_i + d_{i+1}. $$

By using (1) if i is even and Lemma 12 if i is odd, we conclude

$$ \begin{aligned} & -\lambda d_i + d_{i+1} + (1 + \lambda)\gamma - \lambda d_i + d_{i+1} \\ &= -(1 + \lambda)\gamma + 2((1 + \lambda)\gamma - \lambda d_i + d_{i+1}). \end{aligned} $$

Using Lemma 10(ii) gives
$$ -(1 + \lambda)\gamma + 2 \left( (1 + \lambda)\gamma - (1 + \lambda)\frac{\gamma}{\lambda^i} \right) \\ \leq -\gamma(1 + \lambda) = -\gamma\Delta\text{ALG}. $$

If $k$ is even, there are two additional cases which occur when the request is located between the two middle servers $s_{k/2}$ and $s_{k/2+1}$. Note that these cases cannot be covered by the previous ones, since the $\omega$-weights of the servers on both sides of the request are equal.

(f) Let the request be between $s_{k/2}$ and $s_{k/2+1}$, and suppose that $s_{k/2}$ is predicted while the optimal solution serves $r$ with $x_j$ for some $j > k/2$. The change of $\Phi$ is at most

$$ \Delta\Phi \leq \beta\gamma(\omega_{k/2} - \lambda\omega_{k/2}) - \lambda d_{k/2} - d_{k/2}. \quad (5) $$

For the rest of this case, we distinguish two cases according to the parity of $k/2$, and show that $\Delta\Phi \leq -\gamma\Delta\text{ALG}$. If $k/2$ is even, (5) is by Lemma 11 and the definition (1) of $\omega_{k/2}$ equal to

$$ 2\lambda \sum_{j=1}^{k/4} d_{2j-1} - 2 \sum_{j=1}^{k/4-1} d_{2j} - d_{k/2} - \gamma \\ - \left( 2\lambda \sum_{j=1}^{k/4-1} d_{2j} - 2 \sum_{j=1}^{k/4-1} d_{2j+1} + \lambda d_{k/2} + (2+\lambda)\gamma \right) - \lambda d_{k/2} - d_{k/2}. $$

Noting that $2\lambda \sum_{j=1}^{k/4} d_{2j-1} = 2\lambda d_1 + 2\lambda \sum_{j=1}^{k/4-1} d_{2j+1}$ gives

$$ -(3 + \lambda)\gamma + 2 \left( \lambda d_1 + (1 + \lambda) \sum_{j=2}^{k/2} (-1)^{j-1} d_j \right). $$

We conclude that this is equal to $-\gamma(1 + \lambda)$ by Lemma 10(iii). Similarly, if $k/2$ is odd, (5) is by Lemma 12 and the definition (2) of $\omega_{k/2}$ equal to

$$ 2\lambda \sum_{j=1}^{(k/2-1)/2} d_{2j} - 2 \sum_{j=1}^{(k/2-3)/2} d_{2j+1} - d_{k/2} + \gamma \\ - \left( 2\lambda \sum_{j=1}^{(k/2-1)/2} d_{2j-1} - 2 \sum_{j=1}^{(k/2-1)/2} d_{2j} + \lambda d_{k/2} + \lambda\gamma \right) - \lambda d_{k/2} - d_{k/2}. $$

Noting that $2\lambda \sum_{j=1}^{(k/2-1)/2} d_{2j-1} = 2\lambda d_1 + 2\lambda \sum_{j=1}^{(k/2-3)/2} d_{2j+1}$ yields
$$ 
\begin{aligned}
& \gamma - \lambda\gamma + 2 \left( -\lambda d_1 + (1 + \lambda) \sum_{j=2}^{k/2} (-1)^j d_j \right) \\
& = \gamma - \lambda\gamma - 2 \left( \lambda d_1 + (1 + \lambda) \sum_{j=2}^{k/2} (-1)^{j-1} d_j \right).
\end{aligned}
$$

This is equal to $-\gamma(1 + \lambda)$ by Lemma 10(iii).

(g) Let the request be between $s_{k/2}$ and $s_{k/2+1}$, and suppose that $s_{k/2}$ is predicted while the optimal solution serves $r$ with $x_j$ for some $j \le k/2$. The change of $\Phi$ is at most

$$ \Delta\Phi \le \beta\gamma(\lambda\omega_{k/2} - \omega_{k/2}) - \lambda d_{k/2} - d_{k/2}, $$

which is bounded from above by (5) in the previous case. □

## 4.3 Tightness of Theorem 1

We show that our analysis is tight.

**Lemma 17** For any $\lambda \in [0, 1]$, LAMBDADC has a consistency ratio of at least $\alpha(\lambda, k)$.

*Proof* Consider $k$ servers initially at positions $0, 1, -1, 2, -2$, and the request sequence with $k + 1$ requests at positions $0.5, 0, 1, -1, 2, -2$. There is a solution of cost 1 that only moves the server that is initially at 0.

LAMBDADC serves the first request by moving the optimal server from 0 to 0.5 and additionally the one from 1 to $-\lambda/2$. With the second request, the first server is moved back to 0, having moved a total distance of 1, and the server from $-1$ moves to $-1 + \lambda/2$. For the third request, the server from original position 1 returns to this position, etc.

Each server moves back to its initial position $i$ after moving a total distance of $\lambda^{|i|}$. Repeating this example gives the lower bound on the consistency. □

**Lemma 18** For any $\lambda \in [0, 1]$, LAMBDADC has a robustness ratio of at least $\beta(\lambda, k)$.

*Proof* Consider $k$ servers initially located at positions $\beta(\lambda, i) = \sum_{i=0}^{k-1} \lambda^{-i}$, for $i \in \{1, \dots, k\}$, and the request sequence of length $k + 1$ at positions $0, \beta(\lambda, 1) = 1, \beta(\lambda, 2) = 1 + \lambda^{-1}, \dots, \beta(\lambda, k)$. There is a solution of cost 2 that only moves the server that is initially at $\beta(\lambda, 1) = 1$. Consider predictions corresponding always to the rightmost server at the highest position.

LAMBDADC serves the second request by moving both servers from 0 and $\beta(\lambda, 2)$ to $\beta(\lambda, 1)$ as the closest server moves by a distance of 1 and the furthest server, which is predicted, moves by a distance of $1/\lambda$. Similarly, for each request except the last
one, both servers neighboring the request end up serving the request simultaneously. So the *i*-th server moves by a total distance of $2/\lambda^{i-1}$. Repeating this example gives the lower bound on the robustness. □

# 5 Tradeoff Lower Bound for *k* Servers

In this section, we give a lower bound on the consistency-robustness tradeoff and prove Theorem 2. To this end, let $\lambda \in (0, 1]$ and define $\rho(\lambda, k) = \sum_{i=0}^{k-1} \lambda^i$ and $\beta(\lambda, k) = \sum_{i=0}^{k-1} \lambda^{-i}$. Our goal is to prove that a $\rho(\lambda, k)$-consistent algorithm has a robustness ratio of at least $\beta(\lambda, k)$.

We prove this statement for algorithms which are memory-constrained and that satisfy a certain locality property. We emphasize that LAMBDADC satisfies these properties. Informally, we require that a *k*-server algorithm with a certain consistency $\mu(k)$ shall have a consistency $\mu(k')$ on a sub-instance that it serves with $k' < k$ servers. The rationale is to prevent the mere presence of additional unused servers to allow the algorithm to perform poorly on a subinstance served by few servers, as $\mu(k') < \mu(k)$. Hence, such algorithms are expected to present a better performance on a modified instance where some extreme servers are removed and side-effects due to their presence are simulated.

In the following, we make this intuition precise and sketch our worst-case construction.

Given an algorithm $\mathcal{A}$ which is $\mu(k)$-consistent for the *k*-server problem, we define the notion of locally-consistent. Given an instance of the *k*-server problem served by algorithm $\mathcal{A}$, consider any subset $S'$ of $k'$ consecutive servers. We construct an instance $I'$ of the $k'$-server problem based on $I$ and $S'$: If a request of $I$ is predicted to be served by a server in $S'$ then this request is replicated in $I'$. Otherwise, $I'$ requests the position of the closest server in $S'$ after $\mathcal{A}$ served this request in $I$ (in order to take into account side effects due to additional servers in the original instance). Let FTP($I'$) be the cost of serving $I'$ following the predictions of $I'$ (using the closest server in $S'$ if a server that is not in $S'$ was initially predicted). An algorithm is locally-consistent if its total cost on $I$ restricted to the servers in $S'$ is at most $\mu(k') \cdot \text{FTP}(I') + c$, where $c$ can be upper bounded based only on the initial configuration $I'$. We further require that if the initial and final configurations restricted to $S'$ differ by a total distance of $\varepsilon$, then $c = O(k'\varepsilon)$. This is an additional upper bound on the value of $c$, which is related to the spread of the initial configuration, to ensure that this extra budget is not abused by the algorithm. Intuitively, this budget should be used to decrease the spread of the configuration. Note that LAMBDADC is locally-consistent as its behavior in $I$ restricted to the servers in $S'$ is equal to its behavior in $I'$ with $k'$ servers.

The following proof generalizes ideas from the 2-server case (Sect. 3.2) in a non-trivial way. Let $\mathcal{A}$ be a memory-constrained and locally-consistent deterministic algorithm. Recall that a memory-constrained algorithm does not cross servers. We construct an instance that starts with $k$ equidistant servers. First, a point far on the right is requested. Then the initial server locations are requested following specific

<figure><img src="image_8.png" /></figure>
rules until the rightmost server comes back. Predictions correspond to the server initially at the point requested. The consistency of $\mathcal{A}$ limits the possible cost paid before the rightmost server comes back. The locally-consistent definition allows, with technical care, to link the distance traveled by two neighboring servers: the left one travels a total distance at most $\lambda$ times the right one (plus negligible terms). An offline solution can afford to initially shift all servers to the right, and then move only the leftmost server, which $\mathcal{A}$ could not move much. We then repeat this instance, and use the memory-constrained and deterministic characteristics of $\mathcal{A}$ to eliminate constant costs and show the desired robustness lower bound, again with technical care.

We now present a formal and precise proof following the above ideas. We write $\rho(k)$ for $\rho(\lambda, k)$. Let $\mathcal{A}$ be a $\rho(i)$-consistent locally-consistent and memory-constrained deterministic online algorithm for the $i$-server problem on the line, for all $i \le k$. The objective is to show that $\mathcal{A}$ is has a robustness ratio of at least $\beta(\lambda, k)$, with $\beta(\lambda, k) = \sum_{i=0}^{k-1} \lambda^{-i}$.

Let $p_1 \le \dots \le p_{k+1}$ be points on the line with inter-distances $d_1, \dots, d_k$, where for $1 \le i \le k-1$, $d_i = 1$, and $d_k > 1$ is arbitrarily large. We also define an arbitrarily small constant $\epsilon > 0$ and say that a server covers a point $p_i$ if it is at most a distance $\epsilon$ away from it. We refer to smaller positions on the line as left. Let $P := \{p_1, \dots, p_k\}$. In the following we inductively construct an instance. In their initial configuration, that is, at time $t=0$, the $k$ servers, $s_1, \dots, s_k$, are located at $p_1, \dots, p_k$. We assume that servers never overpass each other to simplify the notations. Then, we force the servers to $p_1, \dots, p_{k-1}, p_{k+1}$ (see the memory-constrained definition). The instance terminates when $\mathcal{A}$ places $s_k$ to cover $p_k$. At any time $t > 0$, the next requested point $r_t$ is the leftmost point (that is, the point with the smallest index) which is not covered by any server of $\mathcal{A}$, except in the following two cases. If $p_1$ is not covered and $s_1$ is to the left of $p_2 - \epsilon$ then $r_t$ is the second leftmost uncovered point. If $p_1$ is not covered and $s_1$ covers $p_2$ but did not serve it since leaving $p_1$ then $r_t$ is $p_2$ and $r_{t+1}$ (next in time) is $p_1$. At any time $t > 0$, we denote the instance composed of $r_1, \dots, r_t$ by $I_t$.

At every point in time, we give $\mathcal{A}$ the prediction that suggests serving a request at some point $p_i$ with the server $s_i$. An exception is the first request, where $s_k$ is predicted (note that the first request is always located at $p_{k+1}$). We now show that this construction rule is well-defined.

**Lemma 19** *The construction ends after a finite number of requests.*

*Proof* For the sake of contradiction, assume that the construction does not end after a finite number of requests. Hence, every request $r$ except the first one must be in the set $P$, and by construction, no server covered $r$ in the previous configuration. Thus, the server that serves $r$ must have been moved with some cost at least $\epsilon$, which implies that $\mathcal{A}$ has unbounded cost.

Now consider any infinite instance $I^P$ which starts with a request at $p_{k+1}$ followed by requests contained in $P$. An optimal solution for $I^P$ is to serve the first request with $s_k$ and then to move it immediately back to the set $P$, such that every
point in $\mathcal{P}$ contains a server. Hence, the total cost of an optimal solution is constant. Therefore, the consistency of $\mathcal{A}$ would be infinite, as the prediction given to $\mathcal{A}$ corresponds to the optimal solution, which is a contradiction. $\square$

Due to Lemma 19, we assume for the rest of this section that the construction ends after $n$ steps, and we define $I = I_n$. A exemplary visualization is depicted in Fig. 1.

We first focus on the cost that $\mathcal{A}$ incurs when serving $I$. Let $D_i$ be the distance traveled by the server $s_i$ in $\mathcal{A}$. Using the locally-consistent definition, we show the following relation between $D_i$'s:

**Lemma 20** *For all* $i \le k$, *for* $\varepsilon$ *small enough, we have* $D_1 \le \lambda^{i-1} D_i + O_k(\sqrt{\varepsilon} D_i + d_1)$, 
*where the notation* $O_k(\cdot)$ *treats k as a constant.*

*Proof* Let $i \in \{2, 3, \dots, k\}$ and assume by induction that the relation is true for all $j < i$. Note that it is trivial for $i=1$.

We denote by $\mathcal{A}_i(I)$ the cost of $\mathcal{A}$ restricted to the $i$ leftmost servers. Consider the $i$ leftmost servers and we apply the locally-consistent property of $\mathcal{A}$ on these servers. Let $I'$ be the corresponding instance on $i$ servers, where requests not served by $\{s_1, \dots, s_i\}$ are replaced by requests to the new position of $s_i$.

Consider the algorithm FTP serving $I'$ following the initial predictions as in the locally-consistent definition. There are two types of requests: a point $p_\ell$ for $\ell < i$ is served at no cost by $s_\ell$, and any other request is served by $s_i$. The objective is to upper bound FTP($I'$) by $D_i$ plus negligible terms. Consider all requests different from $p_\ell$ served by $s_i$ in FTP, and let $r_1$ and $r_2$ be two consecutive requests in this set (there can be other requests not belonging to this set between $r_1$ and $r_2$). These requests are based on requests of $I$ outside of $\{p_1 \dots p_i\}$, which means that each of these points (except $p_1$) is covered by a server of $\mathcal{A}$ before the request, and that $s_i$ also went to $r_1$ and $r_2$ in $\mathcal{A}$, at the time at which they are requested in $I'$. A technical difficulty here is that $s_i$ does not need to be exactly at $p_i$ before these requests: it can be within a distance of $\varepsilon$. There are several cases to analyze.

<figure><img src="image_9.png" /><figcaption>**Fig. 1** Instance *I* for $k=3$. The black circles show the initial server configuration. The prediction is drawn green. The blue moves indicate an exemplary schedule of an algorithm</figcaption></figure>
(a) If $p_i$ is not requested between $r_1$ and $r_2$, then FTP pays the shortest path between $r_1$ and $r_2$, so at most how much $s_i$ travels in $\mathcal{A}$.

(b) If $s_i$ goes on $p_i$ between $r_1$ and $r_2$ in $\mathcal{A}$, then FTP also pays at most how much $s_i$ travels in $\mathcal{A}$.

(c) If $p_i$ is requested between $r_1$ and $r_2$ and $s_i$ does not go on $p_i$ in $\mathcal{A}$, we focus on the subinstance $I^*$ starting from the request $r_1$ and ending just before $r_2$ is requested. Let FTP($I^*$), $\mathcal{A}_i(I^*)$ and $D_\ell^*$ be the restrictions of FTP($I$), $\mathcal{A}_i(I)$ and $D_\ell$ to $I^*$. Note that FTP($I^*$) $\le D_i^* + \varepsilon$ as FTP moves $s_i$ to $r_1$ then back to $p_i$ whereas $\mathcal{A}$ needs only to move $s_i$ to $r_1$ and then near $p_i$. The objective is now to show that this additive term $\varepsilon$ is negligible compared to $\mathcal{A}_i(I^*)$, for which we need a further case distinction. If $r_1$ is at least a distance $\sqrt{\varepsilon}$ away from $p_i$, then FTP($I^*$) moves $s_i$ by a distance which is close to $D_i^*$. Specifically, we have $D_i^* \ge 2\sqrt{\varepsilon} - 2\varepsilon \ge \sqrt{\varepsilon}$ for $\varepsilon$ small enough, and the relation FTP($I^*$) $\le D_i^* + \varepsilon$ implies FTP($I^*$) $\le (1 + \sqrt{\varepsilon})D_i^*$. If $r_1$ is at most a distance $\sqrt{\varepsilon}$ away from $p_i$, we get FTP($I^*$) $\le 2\sqrt{\varepsilon} + \varepsilon$ and we distinguish two cases which are slightly different if $i = 2$ or $i > 2$.

(i) If $i > 2$ then the cost of $\mathcal{A}_i$ on $I^*$ is at least $A_i(I^*) \ge D_{i-1}^* > d_{i-1} - \varepsilon = 1 - \varepsilon$ as $p_i$ must have been served by $s_{i-1}$ (previously located near $p_{i-1}$) if it was not served by $s_i$. We therefore obtain FTP($I^*$) $\le 3\sqrt{\varepsilon} \cdot D_{i-1}^*$.

(ii) If $i = 2$, the difference is that $s_1$ may be initially located anywhere between $p_1$ and $p_2$. $s_1$ serves $p_i = p_2$ when it is requested (as this case assumes $s_2$ does not serve $p_2$ in $I^*$), and then must serve $p_1$ by the definition of the instance $I$. Therefore, the cost of $\mathcal{A}_i$ on $I^*$ is at least $A_i(I^*) \ge D_1^* \ge d_1 = 1$. We thus obtain FTP($I^*$) $\le 3\sqrt{\varepsilon} \cdot D_1^*$.

Summing over all subinstances, we conclude

$$ \begin{aligned} \text{FTP}(I') &\le (1 + \sqrt{\varepsilon})D_i + 3\sqrt{\varepsilon} \cdot \sum_{\ell=1}^{i-1} D_\ell \\ &\le D_i + 3\sqrt{\varepsilon} \cdot \mathcal{A}_i(I). \end{aligned} $$

Observe that the initial and final configurations of $\mathcal{A}$ for instance $I$ are identical up to a distance of $d_1$ for $s_1$ and $\varepsilon$ for other servers, thus, differ at most by $\delta = d_1 + k\varepsilon$. The locally-consistent property for $I'$ therefore yields $\mathcal{A}_i(I) \le \rho(i) \cdot \text{FTP}(I') + O(\delta k)$, and inserting our bound on FTP($I'$) gives

$$ \mathcal{A}_i(I) \le \rho(i) \cdot D_i + 3\sqrt{\varepsilon\rho(i)} \cdot \mathcal{A}_i(I) + O(\varepsilon k^2 + d_1 k). $$

For $\varepsilon$ small enough, we have $3\sqrt{\varepsilon\rho(i)} < 1/2$, which implies that $\mathcal{A}_i(I) \le 2\rho(i)D_i + O(\varepsilon k^2 + d_1 k)$. Using this new bound on $\mathcal{A}_i(I)$ on the right-hand side of the above inequality leads to the following bound:

$$ \mathcal{A}_i(I) \le \rho(i)D_i + O(\varepsilon k^2 + d_1 k + \sqrt{\varepsilon\rho(i)}^2 D_i). $$
This inequality and the fact that $A_i(I) = \sum_{\ell=1}^{i} D_{\ell}$ implies

$$ \sum_{\ell=1}^{i-1} D_{\ell} = A_i(I) - D_i \le (\rho(i) - 1)D_i + O(\varepsilon k^2 + d_1 k + \sqrt{\varepsilon \rho(i)^2} D_i). $$

We now use the induction hypothesis to lower bound $D_{\ell}$ by $\lambda^{1-\ell} D_1 + O_k(\sqrt{\varepsilon} D_i + d_1)$ for all $1 \le \ell \le i-1$, and replace $\rho(i)$ by its expression. We use the notation $O_k(\cdot)$ to avoid detailing the irrelevant dependencies on $k$. Note that $\rho(i)$ depends only on $\lambda$ and $k$ so does not appear inside the notation $O_k(\cdot)$. We thus have

$$ \sum_{\ell=1}^{i-1} \frac{1}{\lambda^{\ell-1}} D_1 \le \sum_{\ell=1}^{i-1} \lambda^{\ell} D_i + O_k(\sqrt{\varepsilon} D_i + d_1), $$

and dividing both sides by $\sum_{\ell=0}^{i-2} \lambda^{-\ell}$ concludes the statement, that is,

$$ D_1 \le \lambda^{i-1} D_i + O_k(\sqrt{\varepsilon} D_i + d_1). \square $$

We build the instance $I^{\omega}$ repeating the instance $I^{\omega}$ times, starting directly by the force to $p_1, \dots, p_{k-1}, p_{k+1}$. The predictions for each iteration correspond to the predictions defined in instance $I$. We now bound the optimal cost for this instance.

**Lemma 21** $OPT(I^{\omega}) \le 2d_k + \omega \cdot (D_I + 2 \sum_{i=2}^{k-1} d_i)$.

*Proof* Consider the following schedule for $I^{\omega}$: at each iteration, move $k-1$ servers to $p_2, \dots, p_{k+1}$ and alternate between $p_1$ and $p_2$ with $s_1$. We now analyze how many alternations we need to do in each iteration. By definition of the instance, $p_1$ is only requested if $s_1$ has served $p_2$ since it last left $p_1$. Therefore, the distance traveled by $s_1$ equals $D_1$. At the end of the iteration, we move back the $k-2$ middle servers, giving the target cost. □

Figure 2 shows the better solution for instance $I^{\omega}$, which we use to estimate the optimal solution. Using these preliminary results, we finally prove Theorem 2.

*Proof of Theorem 2* As $\mathcal{A}$ is memory-constrained, its behavior on each iteration of $I$ is identical, $s_k$ is at $p_k$ initially, then the $k$ servers are forced to the points $p_1, \dots, p_{k-1}, p_{k+1}$ before continuing the requests. Therefore $\mathcal{A}$ must pay at least $d_k$ to serve the first force operation, and then must make the same decisions in all iterations.

Using Lemma 21, the robustness ratio of $\mathcal{A}$ for instance $I^{\omega}$ is therefore at least

$$ \frac{\mathcal{A}(I^{\omega})}{OPT(I^{\omega})} \ge \frac{\omega \cdot \sum_{i=1}^{k} D_i}{2d_k + \omega \cdot (D_1 + 2 \sum_{i=2}^{k-1} d_i)} \xrightarrow{\omega \to \infty} \frac{\sum_{i=1}^{k} D_i}{D_1 + 2 \sum_{i=2}^{k-1} d_i}. $$
Consider $d_k$ arbitrarily large (but still small compared to $\omega$). If $D_1$ is bounded by a constant, then the robustness ratio is unbounded, so $\mathcal{A}$ is not robust. Otherwise, the terms $d_i$ become negligible compared to $D_1$, and we show that the limit of the robustness ratio is lower bounded by the desired competitive expression, using Lemma 20 (which implies that $d_1$ is also negligible compared to any $D_i$):

$$ \frac{\mathcal{A}(I^\omega)}{\text{OPT}(I^\omega)} \xrightarrow{d_k \to \infty} \frac{\sum_{i=1}^k D_i}{D_1} \ge \sum_{i=0}^{k-1} \frac{1}{\lambda^i + O_k(\sqrt{\varepsilon} + \frac{d_1}{D_{i+1}})} \xrightarrow{\varepsilon \to 0} \sum_{i=0}^{k-1} \lambda^{-i}. \square $$

Simple algebraic manipulations show that the consistency of LAMBDADC is best possible up to a factor of 2.

**Lemma 22** For every $\lambda \in [0, 1]$, $\alpha(\lambda, k) < 2\rho(\lambda, k)$, and thus, the consistency of LAMBDADC is best-possible up to a factor of 2.

**Proof** First note that for $\lambda = 1$, $\alpha(\lambda, k) = k = \rho(\lambda, k)$. Now suppose that $\lambda < 1$. Applying the formula for the finite geometric series gives

$$ \rho(\lambda, k) = \frac{1 - \lambda^k}{1 - \lambda}. $$

We now prove the result based on the parity of $k$. If $k$ is even, recall that

$$ \alpha(\lambda, k) = 1 + 2 \sum_{i=1}^{k/2-1} \lambda^i + \lambda^{k/2} = 1 + 2 \frac{\lambda - \lambda^{k/2}}{1 - \lambda} + \lambda^{k/2} $$

<figure><img src="image_10.png" /><figcaption>**Fig. 2** Instance $I^\omega$ for $k = 3$. The alternative (better) solution is drawn orange. The prediction and the exemplary moves of the algorithm (blue) are the same as in instance $I$ for each iteration</figcaption></figure>
and, thus,

$$ \frac{\alpha(\lambda, k)}{\rho(\lambda, k)} = \frac{(1 + \lambda^{k/2})(1 - \lambda) + 2(\lambda - \lambda^{k/2})}{1 - \lambda^k} = \frac{1 + \lambda - \lambda^{k/2} - \lambda^{k/2+1}}{1 - \lambda^k} < 2. $$

Otherwise, that is, $k$ is odd, we have

$$ \alpha(\lambda, k) = 1 + 2 \sum_{i=1}^{(k-1)/2} \lambda^i = 1 + 2 \frac{\lambda - \lambda^{(k+1)/2}}{1 - \lambda}, $$

and conclude

$$ \frac{\alpha(\lambda, k)}{\rho(\lambda, k)} = \frac{1 - \lambda + 2(\lambda - \lambda^{(k+1)/2})}{1 - \lambda^k} = \frac{1 + \lambda - 2\lambda^{(k+1)/2}}{1 - \lambda^k} < 2. \square $$

# 6 PAC Learnability of Predictions

We show that predictions in our model are PAC learnable in an agnostic sense with a sample complexity polynomial in the number of requests. Moreover, we give an efficient learning algorithm. Let $\mathcal{D}$ be an unknown distribution of sequences of $n$ requests represented by points in the interval $[0, 1]$. Here, we assume a bounded line as a metric (scaled to $[0, 1]$), which is a restriction but natural in most applications. Further, we assume that we can sample i.i.d. sequences from $\mathcal{D}$.

Let $\mathcal{H} = \{1, \dots, k\}^n$ denote a hypothesis class containing all possible static predictions, that is, the set of all $k$-server solutions for request sequences of length $n$. Let $C_0$ be a known initial configuration. The prediction error for a prediction $\tau \in \mathcal{H}$ on a request sequence $\sigma$ is defined as $\eta_\sigma(\tau) = \text{FTP}(\sigma, \tau) - \text{OPT}(\sigma)$, where FTP($\sigma, \tau$) is the total cost of following the prediction $\tau$ on the sequence $\sigma$ starting in $C_0$, and OPT($\sigma$) is the cost of an optimal solution on $\sigma$ starting in $C_0$. Then, there exists an $\eta_{\max}$ such that $\eta_\sigma(\tau) \le \eta_{\max} \le n$ for all possible sequences $\sigma$ and for all $\tau \in \mathcal{H}$.

We argue that we can use a classical empirical risk minimization (ERM) learning method, see, for example, [50]. The ERM method uses a training set $S = \{\sigma_1, \dots, \sigma_m\}$ of i.i.d. samples from $\mathcal{D}$. Then, it determines a prediction $\tau_p \in \mathcal{H}$ that minimizes the empirical error $\eta_S(\tau) = \frac{1}{m} \sum_{j=1}^m \eta_{\sigma_j}(\tau)$. Since our hypothesis class is finite and the error function bounded, classical results imply that our predictions are PAC learnable in an agnostic sense with a polynomial sample complexity. Further, we show that the problem of finding the prediction minimizing the empirical error within the training set can be reduced to an offline $k$-server problem on a modified request sequence $\tilde{\sigma}$ of length $n$, where the distance between the $l$th and $i$th request in $\tilde{\sigma}$ is given by $\frac{1}{m} \sum_{j=1}^m d(\sigma_j(l), \sigma_j(i))$. This problem can be solved efficiently [23].
**Theorem 23** For any $\epsilon, \delta \in (0, 1)$, a known initial configuration $C_0$ and any distribution $\mathcal{D}$ over the sequences of $n$ requests of known extent, there exists an algorithm which, given an i.i.d. sample of $\mathcal{D}$ of size $m \in \mathcal{O}(\frac{1}{\epsilon^2} \cdot (n \log k - \log \delta)\eta_{\max}^2)$, returns a prediction $\tau_p \in \mathcal{H}$ in polynomial time depending on $k, n$ and $m$, such that with probability of at least $(1 - \delta)$ it holds that $\mathbb{E}_{\sigma \sim \mathcal{D}}[\eta_{\sigma}(\tau_p)] \le \mathbb{E}_{\sigma \sim \mathcal{D}}[\eta_{\sigma}(\tau^*)] + \epsilon$, where $\tau^* = \arg \min_{\tau \in \mathcal{H}} \mathbb{E}_{\sigma \sim \mathcal{D}}[\eta_{\sigma}(\tau)]$.

**Proof** Since the hypothesis class $\mathcal{H}$ is finite with $|\mathcal{H}| = k^n$, and our non-negative error function is bounded by $\eta_{\max}$, classical results [50] imply that $\mathcal{H}$ is agnostically PAC-learnable using the ERM algorithm with a sample complexity of

$$m \le \left\lfloor \frac{2 \log(2|\mathcal{H}|/\delta)\eta_{\max}^2}{\epsilon^2} \right\rfloor \in \mathcal{O}\left( \frac{(n \log k - \log \delta)\eta_{\max}^2}{\epsilon^2} \right).$$

That is, given a sample of size at least $m$, the ERM algorithm outputs with a probability of at least $(1 - \delta)$ a prediction $\tau_p$ such that $\mathbb{E}_{\sigma \sim \mathcal{D}}[\eta_{\sigma}(\tau_p)] \le \mathbb{E}_{\sigma \sim \mathcal{D}}[\eta_{\sigma}(\tau^*)] + \epsilon$ holds, where $\tau^* = \arg \min_{\tau \in \mathcal{H}} \mathbb{E}_{\sigma \sim \mathcal{D}}[\eta_{\sigma}(\tau)]$.

It remains to describe an efficient implementation of the ERM algorithm for our setting. Let $S = \{\sigma_1, \dots, \sigma_m\}$ be a sample drawn i.i.d. from $\mathcal{D}$. We assume that this can be done in polynomial time in $m$. For a sequence $\sigma_j \in S$ let $\sigma_j(i)$ be the position of the $i$th request in $\sigma_j$. We further define for $1 \le \ell \le i \le n$ and $1 \le k' \le k$ the distance functions $\delta_j(\ell, i) = |\sigma_j(\ell) - \sigma_j(i)|$ and $\gamma_j(k', i) = |C_0(k') - \sigma_j(i)|$. The empirical error of a prediction $\tau$ is in our setting defined as

$$\eta_S(\tau) = \frac{1}{m} \sum_{j=1}^{m} \eta_{\sigma_j}(\tau) = \frac{1}{m} \sum_{j=1}^{m} \text{FTP}(\sigma_j, \tau) - \text{OPT}(\sigma_j).$$

The ERM algorithm outputs the prediction $\tau_p \in \mathcal{H}$ that minimizes $\eta_S(\tau)$ as a function over $\mathcal{H}$. Since iterating over all predictions in $\mathcal{H}$ takes exponential time, we compute $\tau_p$ differently. To do so, we first observe that $\frac{1}{m} \sum_{j=1}^{m} \text{OPT}(\sigma_j)$ is independent of $\tau$, thus minimizing $\eta_S(\tau)$ can be reduced to minimizing

$$\begin{align}
& \frac{1}{m} \sum_{j=1}^{m} \text{FTP}(\sigma_j, \tau) \nonumber \\
&= \frac{1}{m} \sum_{j=1}^{m} \sum_{k'=1}^{k} \sum_{i=1}^{n} \left( \xi_{k',i}^{\tau} \cdot \gamma_j(k', i) + \sum_{\ell=1}^{i} \chi_{k',i,\ell}^{\tau} \cdot \delta_j(\ell, i) \right) \tag{6} \\
&= \sum_{k'=1}^{k} \sum_{i=1}^{n} \left( \xi_{k',i}^{\tau} \cdot \frac{1}{m} \sum_{j=1}^{m} \gamma_j(k', i) + \sum_{\ell=1}^{i} \chi_{k',i,\ell}^{\tau} \cdot \frac{1}{m} \sum_{j=1}^{m} \delta_j(\ell, i) \right) \nonumber
\end{align}$$
where $\chi_{k',i,l}^\tau \in \{0, 1\}$ indicates that (that is, it is equal to 1 if) server $k'$ serves the $i$th request of $\sigma_j$ directly after the $l$th request of $\sigma_j$ in $\tau$ and $\xi_{k',i}^\tau \in \{0, 1\}$ indicates that the $i$th request of $\sigma_j$ is the first one that server $k'$ serves in $\tau$.

We now demonstrate that we can efficiently compute a prediction $\tau \in \mathcal{H}$ that minimizes (6). Indeed, observe that (6) is equal to the total cost of the solution $\tau$ for the $k$-server instance that starts in $C_0$ and serves a sequence $\tilde{\sigma}$ of length $n$, where the distance between the $l$th and $i$th request in $\tilde{\sigma}$ is given by $\delta'(l, i) = \frac{1}{m} \sum_{j=1}^m \delta_j(l, i)$ and the distance between the $i$th request in $\tilde{\sigma}$ and the initial position of server $k'$ is given by $\gamma'(k', i) = \frac{1}{m} \sum_{j=1}^m \gamma_j(k', i)$. But this means that any optimal solution $\tilde{\tau}$ for this instance also minimizes (6). Clearly, $\tilde{\tau} \in \mathcal{H}$, and an optimal solution for a $k$-server instance with known distance functions can be computed in $O(kn^2)$ time using a min-cost flow algorithm [23]. $\square$

We remark that a pre-computed static prediction does not include information about the partially revealed input. Thus, this is a rather weak prediction and may not help LAMBDA DC much. The existence of an *adaptive* prediction policy which can be efficiently learned remains an open question. Such a policy would provide much more valuable information to our learning-augmented online algorithm.

# 7 Experiments

We supplement our theoretical results by empirically comparing our learning-augmented algorithm LAMBDA DC with the classical online algorithm ignoring predictions DOUBLE COVERAGE [23] and the previously proposed prediction-based algorithm FTP & DC [6] on real world data.

We implemented FTP & DC [6] with the hyperparameter $\gamma$ equal to 1. The instances are based on the BrightKite-Dataset [21], which is based on check-ins into a location-based social network. We extract sequences with a length of 1000 check-ins, normalize the scaling of latitudes to the interval [0, 4000], and use these values as the positions of the requests on the line. All servers start at the same initial random position.

We generate predictions in a semi-random fashion. Fix two parameters $p$, the number of bins, and $b$, the bin size, and an instance. Our goal is to generate evenly distributed predictions, that is, in each bin $i \in \{1, \dots, p\}$ there are at least five predictions with relative error between $(i-1)b$ and $ib$. Additionally, we use an optimal solution of the instance as the perfect prediction. Given those parameters and an instance, we iteratively sample many predictions with an increasing number of wrong choices with respect to the optimal solution. While this procedure does not find all predictions, especially these with the largest relative error, it gives a good tradeoff between running time and range of prediction error. We set $p = 10$ and $b$ as high as we find for at least 40 instances these evenly distributed predictions. Other instances are discarded.

The results for 2, 10 and 50 servers are displayed in Figs. 3 and 4. They show well that, for a reasonable choice of $\lambda$ ($0.1 \le \lambda \le 0.5$), LAMBDA DC outperforms both DOUBLE COVERAGE and FTP & DC for almost all generated relative prediction errors.

<figure><img src="image_11.png" /></figure>
Further, all algorithms except LAMBDADC for $\lambda = 0.0$ improve by a lazy imple-
mentation. This is no surprise, as this is the only algorithm that only moves a single
server in the non-lazy setting, so there are no postponed moves that can possibly be
improved by a lazy implementation. The actual improvements of the largest mean
empirical ratio for any bin of all algorithms which we discovered in our experiments
are given in Table 1, and are also visualized in Fig. 4 for $k = 50$. Observe that LAMB-
DADC benefits more from the lazy implementation when $\lambda$ gets closer to 1, whereas
the improvements for FTP & DC are between 24 and 28%. We suspect that FTP & DC
only makes few expensive resets in our instances, while LAMBDADC benefits from
many cheap improvements.

8 Conclusion

We show the power of imperfect predictions in designing online algorithms for the *k*-server problem on the line. Our algorithm generalizes the classical DOUBLE-COVERAGE algorithm [23] in an intuitive manner and admits a (nearly) tight error-dependent competitive analysis, based on new potential functions, and it outperforms other methods in the literature. Although we show PAC learnability for static predictions, we leave open whether possibly more powerful adaptive prediction models are learnable.

It would be interesting to see if our results generalize to more general metric spaces. In the traditional online setting without predictions, Chrobak and Larmore [22] presented a *k*-competitive straightforward extension of DOUBLECOVERAGE for tree metrics. Their approach does not work out-of-the-box in the learning-augmented setting, because, unlike in DOUBLECOVERAGE, our algorithm does not move all servers with the same speed. However, by decomposing a single service into multiple rounds with different speed profiles, we can show a generalization of LAMBDADC to trees with an error-dependent competitive ratio of at most $(1 + (k-1)\lambda)\left(1 + \frac{\eta}{\text{OPT}}\right)$, and a tight consistency ratio of $1 + (k-1)\lambda$. However, it remains open whether there exists a

<figure><img src="image_12.png" /><figcaption>Fig. 3 Non-lazy algorithms: means over all empirical competitive ratios per prediction quality</figcaption></figure>
<figure><img src="image_13.png" /><figcaption>Fig. 4 Comparison between lazy and non-lazy implementations for $k = 50$ and $b = 3$</figcaption></figure>

<table><caption>Table 1 Relative improvements of the largest mean empirical competitive ratio for any bin due to lazy implementations</caption><thead><tr><th rowspan="2"></th><th colspan="2">DOUBLECOVERAGE</th><th colspan="2">LAMBDADC (0.1)</th><th colspan="2">LAMBDADC (0.5)</th><th colspan="2">FTP &amp; DC</th></tr><tr><th>n-Lazy</th><th>Lazy</th><th>n-Lazy</th><th>Lazy</th><th>n-Lazy</th><th>Lazy</th><th>n-Lazy</th><th>Lazy</th></tr></thead><tbody><tr><td>k = 2</td><td>1.60<br>35%</td><td>1.03</td><td>1.31<br>16%</td><td>1.10</td><td>1.35<br>22%</td><td>1.035</td><td>1.70<br>27%</td><td>1.23</td></tr><tr><td>k = 101.63</td><td>1.29<br>21%</td><td>1.29</td><td>1.35<br>12%</td><td>1.19</td><td>1.43<br>19%</td><td>1.16</td><td>2.14<br>24%</td><td>1.63</td></tr><tr><td>k = 501.63</td><td>1.29<br>21%</td><td>1.29</td><td>1.45<br>12%</td><td>1.27</td><td>1.44<br>19%</td><td>1.17</td><td>2.29<br>28%</td><td>1.66</td></tr></tbody></table>

reasonable robustness bound. Although the worst example we were able to find for the robustness case is on the line, it seems very difficult to design the required potential function for tree metrics.

Moreover, we focused on memory-constrained algorithms, leaving open a more precise quantification of the power of memory. Finally, the recent success on randomized $k$-server algorithms [15, 17] raises the question whether and how randomized algorithms can benefit from (ML) predictions.

## Omitted Proofs

*Proof of Lemma 10* We prove the statements as follows.

(i) Since

$$ \lambda^{k-1}(\beta - 1) = \lambda^{k-1} \sum_{\ell=1}^{k-1} \lambda^{-\ell} = \sum_{\ell=0}^{k-2} \lambda^{\ell}, $$
we conclude by the definition of $\gamma$ and $d_1$ that

$$ \gamma = \frac{d_1}{\beta - 1} = \frac{2}{(1 + \lambda^{k-2})(\beta - 1)} \sum_{\ell=0}^{k-2} \lambda^{\ell} = \frac{2}{1 + \lambda^{k-2}} \lambda^{k-1}. $$

(ii) Simplifying the right-hand side gives

$$ \begin{aligned} \lambda^{i+1} d_i - \lambda^i d_{i+1} &= \frac{2\lambda^i}{1 + \lambda^{k-2}} \left( \lambda \sum_{\ell=i-1}^{k-1-i} \lambda^\ell - \sum_{\ell=i}^{k-2-i} \lambda^\ell \right) \\ &= \frac{2\lambda^i}{1 + \lambda^{k-2}} \left( \sum_{\ell=i}^{k-i} \lambda^\ell - \sum_{\ell=i}^{k-2-i} \lambda^\ell \right) \\ &= \frac{2\lambda^i}{1 + \lambda^{k-2}} (\lambda^{k-i} + \lambda^{k-i-1}) \\ &= 2 \left( \frac{\lambda^k + \lambda^{k-1}}{1 + \lambda^{k-2}} \right) \\ &= (1 + \lambda) \left( \frac{2\lambda^{k-1}}{1 + \lambda^{k-2}} \right). \end{aligned} $$

Then, Lemma 10(i) concludes the proof.

(iii) Assume that $k$ is even. The right-hand side is equal to

$$ (-1)^{k/2-1} \lambda d_{k/2} + \sum_{j=1}^{k/2-1} (-1)^{j-1} (\lambda d_j - d_{j+1}). $$

By Lemma 10(ii),

$$ (-1)^{k/2-1} \lambda d_{k/2} + (1+\lambda) \sum_{j=1}^{k/2-1} (-1)^{j-1} \frac{\gamma}{\lambda^j}, $$

which is equal to

$$ \frac{1}{\lambda^{k/2-1}} \left( (-1)^{k/2-1} \lambda^{k/2} d_{k/2} + \sum_{j=0}^{k/2-2} (-1)^{k/2-j} (\lambda^j + \lambda^{j+1}) \gamma \right). $$

We proceed by applying a telescoping sum argument. Since $k/2 - (k/2 - 2) = 2$, the last term of the sum $\lambda^{k/2-1}\gamma$ is positive. Similarly, the first term $\lambda^0\gamma$ has the same sign as $(-1)^{k/2-0} = -(-1)^{k/2-1}$. The remaining terms of the sum cancel out. Thus, it remains
$$ \frac{1}{\lambda^{k/2-1}} \left( \lambda^{k/2-1}\gamma + (-1)^{k/2-1}(\lambda^{k/2}d_{k/2} - \gamma) \right). $$

By definition, $d_{k/2} = 2\lambda^{k/2-1}/(1 + \lambda^{k-2})$. Hence, $\lambda^{k/2}d_{k/2}$ is equal to $\gamma$ by Lemma 10(i). We conclude that the expression is indeed equal to $\gamma$. □

**Proof of Lemma 12** We first note that for every $1 \le j \le \lfloor k/2 \rfloor - 1$, applying Lemma 10(ii) with $j$ and $j+1$ yields

$$ \lambda d_j - d_{j+1} = \frac{1+\lambda}{\lambda^j} \gamma = \lambda^2 d_{j+1} - \lambda d_{j+2}. \quad (7) $$

We now prove the statement by induction. As induction base, we prove the claim for $i=3$, that is

$$ \omega_3 = \frac{2\lambda d_2 - d_3 + \gamma}{\beta\gamma} = \frac{2\lambda^2 d_2 - \lambda d_3 + \lambda\gamma}{\beta\gamma\lambda} = \frac{2\lambda d_1 - 2d_2 + \lambda d_3 + \lambda\gamma}{\beta\gamma\lambda}. $$

In the last equality we used that $2(1 + \lambda^2)d_2 = 2\lambda(d_1 + d_3)$ by (7). Now assume that $i > 3$ is odd. By induction hypothesis for $i-2$,

$$ \beta\gamma\lambda \cdot \omega_{i-2} = 2\lambda \sum_{j=1}^{(i-1)/2-1} d_{2j-1} - 2 \sum_{j=1}^{(i-1)/2-1} d_{2j} + \lambda d_{i-2} + \lambda\gamma. \quad (8) $$

Consider the claimed expression for $\beta\gamma\lambda \cdot \omega_i$, that is

$$ 2\lambda \sum_{j=1}^{(i-1)/2} d_{2j-1} - 2 \sum_{j=1}^{(i-1)/2} d_{2j} + \lambda d_i + \lambda\gamma, $$

which we rearrange to

$$ 2\lambda \sum_{j=1}^{(i-1)/2-1} d_{2j-1} - 2 \sum_{j=1}^{(i-1)/2-1} d_{2j} + \lambda d_{i-2} + \lambda\gamma + \lambda d_{i-2} + \lambda d_i - 2d_{i-1}. $$

Replacing the right side of (8) in the above expression gives

$$ \beta\gamma\lambda \cdot \omega_{i-2} + \lambda d_{i-2} + \lambda d_i - 2d_{i-1}. $$

Noting that (7) gives $2(1 + \lambda^2)d_{i-1} = 2\lambda(d_{i-2} + d_i)$ yields together with the definition (2) of $\omega_{i-2}$ the equivalent expression
$$2\lambda^2 \sum_{j=1}^{(i-1)/2-1} d_{2j} - 2\lambda \sum_{j=1}^{(i-3)/2-1} d_{2j+1} - \lambda d_{i-2} + \lambda\gamma + 2\lambda^2 d_{i-1} - \lambda d_{i-2} - \lambda d_i \\ = 2\lambda^2 \sum_{j=1}^{(i-1)/2} d_{2j} - 2\lambda \sum_{j=1}^{(i-3)/2} d_{2j+1} - \lambda d_i + \lambda\gamma.$$

which is indeed equal to $\beta\gamma\lambda \cdot \omega_i$ by definition (2). $\square$

**Proof of Lemma 14** By definition, $\omega_1 = \omega_k = 1$. We now show this property for odd $2 \le i \le k - 1$. Assume that $i$ is odd. By definition, the numerator of $\omega_i$ is equal to

$$2\lambda \sum_{j=1}^{(i-1)/2} d_{2j} - 2 \sum_{j=1}^{(i-3)/2} d_{2j+1} - d_i + \gamma.$$

Using definitions gives

$$\frac{2}{1 + \lambda^{k-2}} \left( \lambda \sum_{j=1}^{(i-1)/2} \sum_{\ell=2j-1}^{k-1-2j} 2\lambda^{\ell} - \sum_{j=1}^{(i-3)/2} \sum_{\ell=2j}^{k-2-2j} 2\lambda^{\ell} - \sum_{\ell=i-1}^{k-1-i} \lambda^{\ell} \right) + \gamma \\ = \frac{2}{1 + \lambda^{k-2}} \left( \sum_{j=1}^{(i-1)/2} \sum_{\ell=2j}^{k-2j} 2\lambda^{\ell} - \sum_{j=1}^{(i-3)/2} \sum_{\ell=2j}^{k-2-2j} 2\lambda^{\ell} - \sum_{\ell=i-1}^{k-1-i} \lambda^{\ell} \right) + \gamma \\ = \frac{2}{1 + \lambda^{k-2}} \left( \sum_{j=1}^{(i-1)/2} 2(\lambda^{k-2j} + \lambda^{k-1-2j}) + \sum_{\ell=i-1}^{k-1-i} 2\lambda^{\ell} - \sum_{\ell=i-1}^{k-1-i} \lambda^{\ell} \right) + \gamma \\ = \frac{2}{1 + \lambda^{k-2}} \left( \sum_{\ell=k-i}^{k-2} 2\lambda^{\ell} + \sum_{\ell=i-1}^{k-1-i} \lambda^{\ell} \right) + \gamma.$$

Since $\beta\gamma = \gamma + d_1 \ge 0$, we conclude that $\omega_i \ge 0$. Further, using the fact that $\sum_{\ell=k-i}^{k-2} \lambda^\ell \le \sum_{\ell=0}^{i-2} \lambda^\ell$ yields

$$\frac{2}{1 + \lambda^{k-2}} \left( \sum_{\ell=k-i}^{k-2} 2\lambda^{\ell} + \sum_{\ell=i-1}^{k-1-i} \lambda^{\ell} \right) + \gamma \le \frac{2}{1 + \lambda^{k-2}} \sum_{\ell=0}^{k-2} \lambda^{\ell} + \gamma = d_1 + \gamma,$$

and we conclude that $\omega_i \le 1$. $\square$

**Author contributions** All authors contributed equally.
**Funding** Open Access funding enabled and organized by Projekt DEAL. Open Access funding enabled and organized by Projekt DEAL. This work was partially supported by the German Science Foundation (DFG) under contract 146371743–TRR 89 Invasive Computing.

**Declarations**

**Conflict of interest** The authors have no Conflict of interest to declare that are relevant to the content of this article.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

**References**

1. Agrawal, P., Balkanski, E., Gkatzelis, V., Tingting, O., Tan, X.: Learning-augmented mechanism design: leveraging predictions for facility location. Math. Oper. Res. **49**(4), 2626–2651 (2024). https://doi.org/10.1287/moor.2022.0225

2. Almanza, M., Chierichetti, F., Lattanzi, S., Panconesi, A., Re, G.: Online facility location with multiple advice. In NeurIPS, 4661–4673 (2021). https://proceedings.neurips.cc/paper/2021/hash/250473494b245120a7eaf8b2e6b1f17c-Abstract.html

3. Antoniadis, A., Boyar, J., Eliás, M., Favrholdt, L.M., Hoeksma, R., Larsen, K.S., Polak, A., Simon, B.: Paging with succinct predictions. In ICML, volume 202 of proceedings of machine learning research, pages 952–968. PMLR (2023). https://proceedings.mlr.press/v202/antoniadis23a.html

4. Antoniadis, A., Coester, C., Eliás, M., Polak, A., Simon, B.: Mixing predictions for online metric algorithms. In ICML, volume 202 of Proceedings of machine learning research, 969–983. PMLR, (2023). https://proceedings.mlr.press/v202/antoniadis23b.html

5. Antoniadis, A., Fischer, C., Tönnis, A.: A collection of lower bounds for online matching on the line. In LATIN, volume 10807 of lecture notes in computer science, 52–65. Springer, 2018. https://doi.org/10.1007/978-3-319-77404-6_5

6. Antoniadis, A., Coester, C., Eliás, M., Polak, A., Simon, B.: Online metric algorithms with untrusted predictions. ACM Trans. Algorithms **19**(2), 19:1–19:34 (2023). https://doi.org/10.1145/3582689

7. Azar, Y., Panigrahi, D., Touitou, N.: Online graph algorithms with predictions. In SODA, 35–66. SIAM (2022). https://doi.org/10.1137/1.9781611977073.3

8. Bampis, E., Escoffier, B., Gouleakis, T., Hahn, N., Lakis, K., Shahkarami, G., Xefteris, M.: Learning-augmented online TSP on rings, trees, flowers and (almost) everywhere else. In ESA, volume 274 of LIPIcs, pages 12:1–12:17. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, (2023). https://doi.org/10.4230/LIPIcs.ESA.2023.12

9. Banerjee, S., Cohen-Addad, V., Gupta, A., Li, Z.: Graph searching with predictions. In ITCS, volume 251 of LIPIcs, pages 12:1–12:24. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, (2023). https://doi.org/10.4230/LIPIcs.ITCS.2023.12

10. Bansal, N., Coester, C., Kumar, R., Purohit, M., Vee, E.: Learning-augmented weighted paging. In SODA, 67–89. SIAM (2022). https://doi.org/10.1137/1.9781611977073.4

11. Bartal, Y., Koutsoupias, E.: On the competitive ratio of the work function algorithm for the k-server problem. Theor. Comput. Sci. **324**(2–3), 337–345 (2004). https://doi.org/10.1016/j.tcs.2004.06.001

12. Bernardini, G., Lindermayr, A., Marchetti-Spaccamela, A., Megow, N., Stougie, L., Sweering, M.: A universal error measure for input predictions applied to online graph problems. In NeurIPS, (2022). https:// papers.nips.cc/paper_files/paper/2022/hash/15212bd2265c4a3ab0dbc1b1982c1b69-Abstract-CONFERENCE.html
13. Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, United Kingdom (1998)

14. Brand, J.v.d., Forster, S., Nazari, Y., Polak, A.: On dynamic graph algorithms with predictions. In SODA, 3534–3557. SIAM (2024). https://doi.org/10.1137/1.9781611977912.126

15. Bubeck, S., Coester, C., Rabani, Y.: Shortest paths without a map, but with an entropic regularizer. In FOCS, 1102–1113. IEEE (2022). https://doi.org/10.1109/FOCS54457.2022.00036

16. Bubeck, S., Coester, C., Rabani, Y.: The randomized k-server conjecture is false! In STOC, 581–594. ACM, (2023). https://doi.org/10.1145/3564246.3585132

17. Bubeck, S., Cohen, M.B., Lee, Y.T., Lee, J.R., Madry, A.: k-server via multiscale entropic regularization. In STOC, 3–16. ACM (2018). https://doi.org/10.1145/3188745.3188798

18. Buchbinder, N., Coester, C., (Seffi) Naor, J.: Online k-taxi via double coverage and time-reverse primal-dual. In IPCO, volume 12707 of Lecture notes in computer science, 15–29. Springer, (2021). https://doi.org/10.1007/978-3-030-73879-2_2

19. Castenow, J., Feldkord, B., Knollmann, T., Malatyali, M., Meyer auf der Heide, F.: The k-server with preferences problem. In SPAA, 345–356. ACM (2022). https://doi.org/10.1145/3490148.3538595

20. Chiplunkar, A., Vishwanathan, S.: Randomized memoryless algorithms for the weighted and the generalized k-server problems. ACM Trans. Algorithms 16(1), 14:1-14:28 (2020)

21. Cho, E., Myers, S.A., Leskovec, J.: Friendship and mobility: user movement in location-based social networks. In KDD, 1082–1090. ACM (2011). https://doi.org/10.1145/2020408.2020579

22. Chrobak, M., Larmore, L.L.: An optimal on-line algorithm for k-servers on trees. SIAM J. Comput. 20(1), 144–148 (1991). https://doi.org/10.1137/0220008

23. Chrobak, M., Karloff, H.J., Payne, T.H., Vishwanathan, S.: New results on server problems. SIAM J. Discret. Math. 4(2), 172–181 (1991). https://doi.org/10.1137/0404017

24. Chrobak, M., Haney, S., Liaee, M., Panigrahi, D., Rajaraman, R., Sundaram, R., Young, N.E.: Online paging with heterogeneous cache slots. Algorithmica 87(1), 89–131 (2025). https://doi.org/10.1007/s00453-024-01270-z

25. Coester, C., Koutsoupias, E.: The online [CDATA[k]]k-taxi problem. In STOC, 1136–1147. ACM (2019). https://doi.org/10.1145/3313276.3316370

26. Coester, C., Koutsoupias, E.: Towards the k-server conjecture: a unifying potential, pushing the frontier to the circle. In ICALP, volume 198 of LIPIcs, 57:1–57:20. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, (2021). https://doi.org/10.4230/LIPIcs.ICALP.2021.57

27. Costa, M.L., Padilha, C., Melo, J.D., Neto, A.: Hierarchical reinforcement learning and parallel computing applied to the k-server problem. IEEE Lat. Am. Trans. 14(10), 4351–4357 (2016)

28. Dinitz, M., Im, S., Lavastida, T., Moseley, B., Vassilvitskii, S.: Faster matchings via learned duals. In NeurIPS, 10393–10406 (2021). https://proceedings.neurips.cc/paper/2021/hash/5616060fb8ae85d93f334e7267307664-Abstract.html

29. Eberle, F., Lindermayr, A., Megow, N., Nölke, L., Schlöter, J.: Robustification of online graph exploration methods. In AAAI, 9732–9740. AAAI Press (2022). https://doi.org/10.1609/aaai.v36i9.21208

30. Gkatzelis, V., Kollias, K., Sgouritsa, A., Tan, X.: Improved price of anarchy via predictions. In EC, 529–557. ACM (2022). https://doi.org/10.1145/3490486.3538296

31. Henzinger, M., Saha, B., Seybold, M.P., Ye, C.: On the complexity of algorithms with predictions for dynamic graph problems. In ITCS, volume 287 of LIPIcs, 62:1–62:25. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, (2024). https://doi.org/10.4230/LIPIcs.ITCS.2024.62

32. Im, S., Kumar, R., Petety, A., Purohit, M.: Parsimonious learning-augmented caching. In ICML, volume 162 of Proceedings of Machine Learning Research, 9588–9601. PMLR (2022). https://proceedings.mlr.press/v162/im22a.html

33. Junior, M.L.L., Neto, A.D.D., de Melo, J.D.: The k-server problem: a reinforcement learning approach. In IJCNN, 798–802. IEEE (2005). https://doi.org/10.1109/IJCNN.2005.1555954

34. Koutsoupias, E.: The k-server problem. Comput. Sci. Rev. 3(2), 105–118 (2009). https://doi.org/10.1016/j.cosrev.2009.04.002

35. Koutsoupias, E., Papadimitriou, C.H.: On the k-server conjecture. J. ACM 42(5), 971–983 (1995). https://doi.org/10.1145/210118.210128

36. Koutsoupias, E., Taylor, D.S.: The CNN problem and other k-server variants. Theor. Comput. Sci. 324(2–3), 347–359 (2004). https://doi.org/10.1016/j.tcs.2004.06.002

37. Kraska, T., Beutel, A., Chi, Ed H., Dean, J., Polyzotis, N.: The case for learned index structures. In SIGMOD Conference, 489–504. ACM (2018). https://doi.org/10.1145/3183713.3196909
38. Lindermayr, A., Megow, N., Simon, B.: Double coverage with machine-learned advice. In ITCS, volume 215 of LIPIcs, 99:1–99:18. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, (2022). https://doi.org/10.4230/LIPIcs.ITCS.2022.99

39. Lindermayr, A., Megow, N.: ALPS paper collection, (2023). https://algorithms-with-predictions.github.io/

40. Lindermayr, A.: Learning-augmented Online Algorithms for the 2-server Problem on the Line and Generalizations. Master’s thesis, University of Bremen, Germany (2020)

41. Lins, R., Dória, A., de Melo, J.D.: Deep reinforcement learning applied to the k-server problem. Expert Syst. Appl. 135, 212–218 (2019)

42. Lykouris, T., Vassilvitskii, S.: Competitive caching with machine learned advice. J. ACM 68(4), 24:1-24:25 (2021). https://doi.org/10.1145/3447579

43. Mahdian, M., Nazerzadeh, H., Saberi, A.: Allocating online advertisement space with unreliable estimates. In EC, 288–294. ACM (2007). https://doi.org/10.1145/1250910.1250952

44. Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for on-line problems. In STOC, 322–333. ACM (1988). https://doi.org/10.1145/62212.62243

45. Manasse, M.S., McGeoch, L.A., Sleator, D.D.: Competitive algorithms for server problems. J. Algorithms 11(2), 208–230 (1990). https://doi.org/10.1016/0196-6774(90)90003-W

46. Mitzenmacher, M., Vassilvitskii, S.: Algorithms with predictions. In Beyond the Worst-Case Analysis of Algorithms, 646–662. Cambridge University Press, (2020). https://doi.org/10.1017/9781108637435.037

47. Purohit, M., Svitkina, Z., Kumar, R.: Improving online algorithms via ML predictions. In NeurIPS, 9684–9693, (2018). https://proceedings.neurips.cc/paper/2018/hash/73a427badebe0e32caa2e1fc7530b7f3-Abstract.html

48. Raghvendra, S., Sowle, R.: A scalable work function algorithm for the k-server problem. In SWAT, volume 227 of LIPIcs, 30:1–30:20. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, (2022). https://doi.org/10.4230/LIPIcs.SWAT.2022.30

49. Rohatgi, D.: Near-optimal bounds for online caching with machine learned advice. In SODA, 1834–1845. SIAM (2020). https://doi.org/10.1137/1.9781611975994.112

50. Shalev-Shwartz, S., Ben-David, S.: Understanding Machine Learning - From Theory to Algorithms. Cambridge University Press, United Kingdom (2014)

51. Sleator, D.D., Tarjan, R.E.: Amortized efficiency of list update and paging rules. Commun. ACM 28(2), 202–208 (1985). https://doi.org/10.1145/2786.2793

52. Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134–1142 (1984). https://doi.org/10.1145/1968.1972

53. Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16(2), 264–280 (1971)

54. Xu, C., Moseley, B.: Learning-augmented algorithms for online steiner tree. In AAAI, 8744–8752. AAAI Press (2022). https://doi.org/10.1609/aaai.v36i8.20854

55. Zhang, W., Cheng, Y.: A new upper bound on the work function algorithm for the k-server problem. J. Comb. Optim. 39(2), 509–518 (2020). https://doi.org/10.1007/s10878-019-00493-z

**Publisher's Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## Authors and Affiliations

Alexander Lindermayr¹ · Nicole Megow¹ · Bertrand Simon²

<figure><img src="image_14.png" /></figure>

Alexander Lindermayr
linderal@uni-bremen.de

Nicole Megow
nmegow@uni-bremen.de

Bertrand Simon
bertrand.simon@cnrs.fr

<figure><img src="image_15.png" /></figure>
¹ Faculty of Mathematics and Computer Science, University of Bremen, Bibliothekstraße 5,
28359 Bremen, Germany

² IN2P3 Computing Center, CNRS, 21 Avenue Pierre de Coubertin, 69100 Villeurbanne, Fraace