Recently, there has been a lot of interest in using machine learning to design improved algorithms for various computational problems. This includes work on data structures Kraska et al. (2018); Mitzenmacher (2018), online algorithms Lykouris and Vassilvitskii (2018); Purohit et al. (2018); Gollapudi and Panigrahi (2019a); Rohatgi (2020), combinatorial optimization Khalil et al. (2017); Balcan et al. (2018), similarity search Wang et al. (2016), compressive sensing Mousavi et al. (2015); Bora et al. (2017) and streaming algorithms Hsu et al. (2019). This body of work is motivated by the fact that modern machine learning methods are capable of discovering subtle structure in collections of input data, which can be utilized to improve the performance of algorithms that operate on similar data.
In this paper we focus on learning-augmented online algorithms. An on-line algorithm makes non-revocable decisions based only on the part of the input seen so far, without any knowledge of the future. It is thus natural to consider a relaxation of the model where the algorithm has access to (imperfect) predictors of the future input that could be used to improve the algorithm performance. Over the last couple of years this line of research has attracted growing attention in the machine learning and algorithms literature, for classical on-line problems such as caching Lykouris and Vassilvitskii (2018); Rohatgi (2020), ski-rental and scheduling Purohit et al. (2018); Gollapudi and Panigrahi (2019b); Lattanzi et al. (2020) and graph matching Kumar et al. (2019). Interestingly, most of the aforementioned works conclude that the "optimistic" strategy of simply following the predictions, i.e., executing the optimal solution computed off-line for the predicted input, can lead to a highly sub-optimal performance even if the prediction error is small 1 . For instance, for the caching problem, even a single misprediction can lead to an unbounded competitive ratio Lykouris and Vassilvitskii (2018).
In this paper we show that, perhaps surprisingly, the aforementioned "optimistic" strategy leads to nearoptimal performance for some well-studied on-line problems. We focus on the problem of page migration Black and Sleator (1989) (a.k.a. file migration Bienkowski (2012) or 1-server with excursions Manasse et al. (1990)). Here, the algorithm is given a sequence s of points (called requests) s 1 , s 2 , . . . from a metric space (X, d), in an online fashion. The state of the algorithm is also a point from (X, d). Given the next request s i , the algorithm moves to its next state a i (at the cost of D • d(a i-1 , a i ), where D is a parameter), and then "satisfies" the request s i (at the cost of d(a i , s i )). The objective is to satisfy all requests while 1 To the best of our knowledge the only problem for which this strategy is known to result in an optimal algorithm is the online bipartite matching, see Section 1.2 for more details minimizing the total cost. The problem has been a focus on a large body of research, see e.g., Awerbuch et al. (1993); Westbrook (1994); Chrobak et al. (1997); Bartal et al. (1997); Khorramian and Matsubayashi (2016); Bienkowski et al. (2017). The best known algorithms for this problem have competitive ratios of 4 (a deterministic algorithm due to Bienkowski et al. (2017)), 3 (a randomized algorithm against adaptive adversaries due to Westbrook (1994)) and 2.618 . . . (a randomized algorithm against oblivious adversaries due to Westbrook (1994)). The original paper Black and Sleator (1989) also showed that the competitive ratio of any deterministic algorithm must be at least 3, which was recently improved to 3 + for some > 0 by Matsubayashi (2015).
Suppose that we are given a predicted request sequence ŝ that, in each interval of length D, differs from the actual sequence s on at most a fraction q of positions, where , q ∈ (0, 1) are the parameters (note that the lower the values of and q are, the stronger our assumption is). Under this assumption we show that the optimal off-line solution for ŝ is a (1 + )(1 + O(q))competitive solution for s as long as the parameter q > 0 is a small enough constant. Thus, the competitive ratio of this prediction-based algorithm improves over the state of the art even if the number of errors is linear in the sequence length, and tends to 1 when the error rate tends to 0.foot_0 Furthermore, to make the algorithm robust, we also design a "fallback option", which is triggered if the input sequence violates the aforementioned assumption (i.e., if the fraction of errors in the suffix of the current input sequence exceeds q). The fallback option ensures that the competitive ratio of the algorithm for any input sequence is at most O(1/q). Thus, our final algorithm produces a nearoptimal solution if the prediction error is small, while guaranteeing a constant competitive ratio otherwise.
For the case when the underlying metric is uniform, i.e., all distances between distinct points are equal to 1, we further improve the competitive ratio to 1+ O(q) under the assumption that each interval of length D differs from the actual sequence in at most qD positions. That is, the parameter is not needed in this case. Moreover, any algorithm has a competitive ratio of at least 1 + Ω(q). It is natural to wonder whether the same guarantees hold even when the predicted sequence differs from the actual sequence on at most a fraction of q positions distributed arbitrarily over ŝ, as opposed to over chunks of length εD. We construct a simple example that shows that such a relaxed assumption results in the same lower bound as for the classical problem.
Multiple variations of the page migration problem have been studied over the years. For example, if the page can be copied as well as moved, the problem has been studied under the name of file allocation, see e.g., Bartal et al. (1995); Awerbuch et al. (2003); Lund et al. (1998). Other formulations add constraints on nodes capacities, allow dynamically changing networks etc. See the survey Bienkowski (2012) for an overview.
There is a large body of work concerning on-line algorithms working under stochastic or probabilistic assumptions about the input Unc (2016). In contrast, in this paper we do not make such assumptions, and allow worst case prediction errors (similarly to Lykouris and Vassilvitskii (2018); Kumar et al. (2019); Purohit et al. (2018)). Among these works, our prediction error model (bounding the fraction of mispredicted requests) is most similar to the "agnostic" model defined in Kumar et al. (2019). The latter paper considers online matching in bipartite graphs, where a prediction of the graph is given in advance, but the final input graph can deviate from the prediction on d vertices. Since each vertex impacts at most one matching edge, it directly follows that d errors reduce the matching size by at most d. In contrast, in our case a single error can affect the cost of the optimum solution by an arbitrary amount. Thus, our analysis requires a more detailed understanding of the properties of the optimal solution.
Multiple papers studied on-line algorithms that are given a small number of bits of advice Boyar et al. (2017) and show that, in many scenarios, this can improve their competitive ratios. Those algorithms, however, typically assume that the advice is error-free.
In the classical version, the algorithm is given a sequence s of points (called requests) s = (s i ) i∈[n] from a metric space (X, d), in an online fashion. The state of the algorithm (i.e., the page), is also a point from (X, d). Given the next request s i , the algorithm moves to its next state a i (at the cost of D • d(a i-1 , a i ), where D > 1 is a parameter), and then "satisfies" the request s i (at the cost of d(a i , s i )). The objective is to satisfy all requests while minimizing the total cost. We can consider a version of this problem where the algorithm is given, prior to the arrival of the requests, a predicted sequence ŝ = (ŝ i ) i∈ [n] . The (final) sequence s is generated adversarially from ŝ and an arbitrary adversarial sequence s = (s * i ) i∈ [n] . That is either s i = ŝi or s i = s * i . The initial input to the (online) algorithm is ŝ. In addition, at every step i, the algorithm receives the request s i for which it outputs in the same step the location from where it serves the request. If we do not make any assumptions on how well s is predicted by ŝ, then the problem is no easier than the classical online version. On the other hand, if s = ŝ, then one obtains an optimal online algorithm, by simply computing the optimal offline algorithm. The interesting regime lies in between these two cases. We will make the following assumption throughout the paper, which roughly speaking demands that a 1 -q fraction of the input is correctly predicted and that the q fraction of errors is somewhat spread out. Definition 1 (Number of mismatches m(•)). Let I be an interval of indices. We define m(I) def = t∈I 1 st =ŝt to be the number of mismatches between s and ŝ within the interval I. Assumption 1. Consider an interval I of s of length εD. It holds that for any I we have m(I) ≤ qεD. Remark 1. Relaxing Assumption 1 by allowing the adversary to change an arbitrary q fraction of the input results in the same lower bound as for the classical problem. To see this, consider an arbitrary instance on qn elements that gives a lower bound of c in the classical problem. Call this sequence of elements adversarial. Let ŝ consists of n elements being equal to the starting point. That is, ŝ is simply the starting position replicated n times. Let s be equal to the sequence ŝ whose suffix of length qn is replaced by the adversarial sequence. Now, on s defined in this way no algorithm can be better than c-competitive. Hence, in general this relaxation of Assumption 1 gives no advantage.
Our main results hold for general metric space, where for all p, p , p ∈ X all of the following hold: d(p, p) = 0, d(p, p ) > 0 for p = p , d(p, p ) = d(p , p), and d(p, p ) ≤ d(p, p ) + d(p , p ). We obtain better results for uniform metric space, where, d(p, p ) = 1 for p = p .
Given a sequence s, we use s i to denote the i-th element of s. For integers i and j, such that 1 ≤ i ≤ j, we use s [i,j] to denote the subsequence of s consisting of the elements s i , . . . , s j .
Let p 0 denote the start position for all algorithms, i.e., the position of the page at time 0.
Given an algorithm B that pays cost C for serving n requests, we denote by C t1,t2 the cost paid by B during the interval [t 1 , t 2 ]. We sometimes abuse notation and write C t as a shorthand for C 0,t . In particular, C denotes C 0,n as well as C n . This notation is the most often used in the context of our algorithm ALG and the optimal solution OPT, whose total serving costs are A and O, respectively.
We now present our main algorithm and provide intuition about its correctness.
Our two main contributions are: algorithm ALG that is (1 + O(q))-competitive provided Assumption 1; and, a black-box reduction from ALG to a O(1/q)competitive algorithm ALG robust when Assumption 1 does not hold. In Section 3.1 we present an overview of ALG, while an overview of ALG robust is given in Section 3.2.
Algorithm ALG (given as Algorithm 1) simply computes the optimal offline solution based on ŝ and moves pages accordingly.
Algorithm 1 ALG(s i , ŝ) Input:
• Request s i
• A prediction ŝ (s and ŝ are defined in Section 2) 1: Let a i be the position of the page in the optimal offline algorithm at the i-th request with respect to ŝ. 2: Move the page to a i and serve the request s i .
The main challenge in proving that ALG still performs well in the online setting lies in leveraging the optimality of ALG with respect to the offline sequence. The reason for this is that, due to s and ŝ not being identical, OPT and ALG may be on different page locations throughout all the requests. In addition to that, we have no control over which q fraction of any interval of length D is changed nor to what it is changed. In particular, if s i = ŝi , then s i and ŝi could be very far from each other. To circumvent this, we use the following way to argue about the offline optimality, that is, about the optimality computed with respect to ŝ.
We think of ALG (OPT, respectively) as a sequence of page locations that are defined with respect to ŝ (s, respectively). These page locations do not change even if, for instance, the i-th online request to ALG deviates from ŝi . Let A t (O t , respectively) be the cost of ALG (OPT, respectively) serving t requests given by s [1,t] . Similarly, let Ât ( Ôt , respectively) be the cost of ALG (OPT, respectively) for serving the oracle subsequence ŝ[1,t] . In particular, A n is the cost of ALG (optimal on ŝ) on the final sequence s, whereas Ôn is the cost of the optimal algorithm for s on the predicted sequence ŝ. It is convenient to think of Ôn as the 'evil twin' of A n .
We have, due to optimality of ALG on the offline sequence,
(1)
The intuition behind the right-hand side of inequality above is best explained pictorially, which we do in Fig. 1. Here ALG is at a and OPT is at o. In the depicted example the actual request is s while the predicted one is ŝ. This causes A n -Ân to increase, however, at the same time, Ôn -O n decreases by almost the same amount. 3 In fact, one can show that for such a request the right hand side of Eq. ( 1) will increase by no more than 2d(a, o). For requests that are predicted correctly, i.e., s = ŝ, the costs of ALG and OPT do not change. It remains to bound d(a t , o t ), which we do next. By triangle inequality, it holds that
be the total sum of moving costs for both OPT and ALG for the requests in the interval (t i-1 , t i ]. As a reminder (see Definition 1), for a given interval I, m(I) is the number of mismatches between s and ŝ within I. From Eq. (3), we derive
We would like the right hand side of Eq. ( 5) to be small, implying that A n -O n is small as well. To understand the nature of the right hand side of Eq. ( 5) and what is required for it to be small, assume for a moment that m((t i-1 , t i ]) = α(t i -t i-1 ). Then, the rest of the summation telescopes to A n -O n , and o a s ŝ Eq. ( 5) reduces to
is sufficiently small, e.g., α ≤ 2q, then we are able to upper-bound Eq. ( 5) by 4q(A n + O n ) and derive
which gives the desired competitive factor.
So, to utilize Eq. ( 5), in our proof we will focus on showing that m((t i-1 , t i ]) is sufficiently smaller than t i -t i-1 . However, this can be challenging as OPT is allowed to move often, potentially on every request which results in t i -t i-1 being very small. But, if t i -t i-1 is too small, then Assumption 1 gives no information about m((t i-1 , t i ]). However, if intervals t i -t i-1 are large enough, e.g., at least βD for some positive constant β, then from Assumption 1 we would be able to conclude that α = O(q). Since in principle OPT can move in every step, we design 'lazy' versions of OPT and ALG that only move O(1) times in any interval of length D. This will enable us to argue that t i -t i-1 is not too small. It turns out that the respective competitive factors of the lazy versions with respect to the original versions is very close, allowing us prove
We now describe ALG robust . This algorithm follows a "lazy" variant of ALG as long as Assumption 1 holds, and otherwise switches to ALG online . Instead of using ALG directly, we use a 'lazy' version of ALG that works as follows: Follow the optimal offline solution given by ALG with a delay of 6qD steps. Let ALG lazy be the corresponding algorithm. We point out that performing some delay with respect to ALG is crucial here. To see that, consider the following example in the case of uniform metric spaces: s = {0} n and ŝ = {1} n , and let the starting location be 0. According to ALG, the page should be moved from 0 to 1 in the very beginning, incurring the cost of D. On the other hand, OPT never moves from 0. If ALG robust would follow ALG until it realizes that the fraction of errors is too high, it would already pay the cost of at least D, leading to an unbounded competitive ratio. However, if ALG robust delays following ALG, then it gets some "slack" in verifying whether the predicted sequence properly predicts requests or not. As a result, when Assumption 1 holds, this delay increases the overall serving cost by a factor O(1 + O(q)), but in turn achieves a bounded competitive ratio when this assumption does not hold.
While serving requests, ALG robust also maintains the execution of ALG online , i.e., ALG robust maintains where ALG online would be at a given point in time, in case a fallback is needed. Now ALG robust simply executes ALG lazy unless we find a violation of Assumption 1 is detected. Once such a violation is detected, the algorithm switches to ALG online by moving its location to ALG online 's current location. From there on ALG online is executed.
We now present the intuition behind the proof for the competitive factor of the algorithm.
In this case ALG robust is ALG lazy , and the analysis boils down to proving competitive ratio of ALG lazy . We show that ALG lazy is (1 + O(q))-competitive to ALG, which is, as we argued in the previous section, 1 + O(q) competitive to OPT. To see this, we employ the following charging argument: whenever ALG moves from a to a it pays D • d(a, a ). The lazy algorithm eventually pays the same moving cost of less.
However, in addition, the serving cost of ALG lazy for each of the 6qD requests is potentially increased, as ALG lazy is not at the same location as ALG. Nevertheless, by triangle inequality, the cost due to the movement from a to a of ALG reflect to an increase in the serving cost of ALG lazy by at most d(a, a ). In total over all the 6qD requests and per each move of ALG from a to a , ALG lazy pays at most 6qDd(a, a ) extra cost compared to ALG. Considering all migrations, this gives a 1 + O(q) competitive factor.
The case where Assumption 1 is violated (say at time t ) is considerably more involved. We then have
and we seek to upper-bound each of these terms by O(OPT/q). While the upper-bound holds directly for ALG online (t + 1, n), showing the upper-bound for other terms is more challenging.
The key insight is that, due to the optimality of ALG,
which can be proven as follows. If ALG migrates its page to a location that is far from the starting location p 0 , then there have to be, even when taking into account noise, at least 4qD page requests that are far from p 0 . OPT also has to serve these requests (either remotely or by moving), and hence has to pay a cost of at least qD • d(a, p 0 ). Equipped with this idea, we can now bound D • d(a, a ) in terms of OPT(t )/q. To bound ALG lazy (0, t ) we need one more idea. Namely, we compare ALG lazy (0, t ) to the optimal solution that has a constraint to be at the same position as ALG lazy at time t . A formal analysis is given in Appendix B.
Now we analyze ALG (Algorithm 1). As discussed in Section 3.1, our main objective is to establish Eq. ( 5), which we do in Section 4.1. That upper-bound will be directly used to obtain our result for uniform metric spaces, as we present in Appendix A.1. To construct our algorithm for general-metric spaces, in Appendix A.2 we build on ALG by first designing its "lazy" variant. As the final result, we show the following. Recall that q is the fraction of symbols that the adversary is allowed to change in any sequence of length εD of the predicted sequence. Theorem 2. If Assumption 1 holds with respect to parameter ε, then we obtain the following results:
(A) There exists a (1 + ε) • (1 + O(q))-competitive algorithm for the online page migration problem.
(B) There exists a (1 + O(q))-competitive algorithm for the online page migration problem in uniform metric spaces.
We defer the proof of Theorem 2 to Appendix A. Note that in the prediction-free case Matsubayashi (2015) show that the competitive ratio of any deterministic algorithm must be at least 3 + for some > 0. In the case of having access to predictions, Theorem 2 is asymptotically optimal with respect to q. Namely, any algorithm is at least 1 + Ω(q) competitive; even in the uniform metric case. To see this consider the following binary example where the algorithm starts at position 0. The advice is ŝ = 111
In the first case OPT simply stays at 0 since moving costs D; in the second case, OPT goes immediately to 1. Note that ALG can only distinguish between the sequences after (1 -q)D steps at which point it is doomed to have an additional cost of qD with probability at least 1/2 depending on the sequence s.
4.1 Establishing Eq. ( 5)
In our proofs we will use the following corollary of Assumption 1.
Corollary 3. If Assumption 1 holds, then for any interval I of length > εD it holds m(I) ≤ 2q .
Proof. This statement follows from the fact that each such I can be subdivided into k ≥ 1 intervals of length exactly εD and at most one interval I of length less than εD. On one hand, the total number of mismatches for these intervals of length exactly εD is upper-bounded by qkεD ≤ q . On the other hand, since I is a subinterval of an interval of length εD, it holds m(I ) ≤ qεD < q . The claim now follows.
Most of our analysis in this section proceeds by reasoning about intervals where neither ALG nor OPT moves. Let t 1 , t 2 . . . be the time steps at which either OPT or ALG move. The final product of this section will be an upper-bound on A n -O n as given by Eq. ( 5) 4 , i.e.,
.
We begin by rewriting and upper-bounding A t -O t as follows
where we used that Ât ≤ Ôt as Ât is the optimum for ŝ. Consider a fixed interval I = (t i-1 , t i ]. Then, by triangle inequality, it holds
Let c
(ti-1,ti] move be the sum of moving costs for OPT and 4 As a reminder, At (Ot, respectively) is the cost of ALG (OPT, respectively) at time for the sequence s
where the inequality comes from Eq. ( 8) applied to every time step in (t i-1 , t i ] and the fact that ALG or OPT must have moved inducing a cost of at least c
move . The following notation is used to represent the difference between serving s i and ŝi by ALG
Note that this holds even when ALG moves since the moving costs for the oracle sequence and on the final sequence are the same and therefore cancel each other out. Similarly to
Consider now any t ∈ [1, n]. By triangle inequality we have
Recall that, for a given interval I the function m(I) denotes the number of mismatches between s and ŝ within I (see Definition 1). Now, as for t such that
This establishes the desired upper-bound on A n -O n . As discussed in Section 3.1, this upper-bound is used to derive our non-robust results for uniform (Appendix A.1) and general (Appendix A.2) metric spaces. The main task in those two sections will be to show that m((t i-1 , t i ]) is sufficiently smaller than t i -t i-1 .
We evaluate our approach on two synthetic data sets, and compare it to the state of the art algorithm for page migration due to Westbrook Westbrook (1994).
The two data sets are obtained by generating "predicted" sequences of points in the plane, and then perturbing each point by independent Gaussian noise to obtain "actual" sequences. The predicted sequence is fed to our algorithm, while the actual sequence forms an input of the online algorithm. Recall that our algorithm sees the actual sequence only in the online fashion.
The predicted sequences of the two sets of points are generated as follows:
1. Line process: the t-th point ( X1 (t), X2 (t)) is equal to (t, 0).
2. Brownian motion process: the t-th point X(t) is equal to X(t -1) + (∆ 1 (t), ∆ 2 (t)), where ∆ t (t) and ∆ 2 (t) are i.i.d. random variables chosen from N (0, 1).
Note that the predicted line process is completely deterministic whereas the Brownian motion points has, by definition, Gaussian noise. In both cases, the actual sequence is generated by adding (additional) Gaussian noise to the predicted sequence: the t-th request X(t) in the actual sequence is equal to X(t)+(N 1 (t), N 2 (t)), where N 1 (t), N 2 (t) are i.i.d. random variables chosen The predicted sequence is in blue, the actual sequence is in red.
from N (0, σ 2 ). The value of σ varies, depending on the specific experiment. An example Brownian motion sequence is depicted in Fig. 2.
We use the two data sets to compare the following three algorithms:
• Predict refers to our algorithm, which computes the optimum solution for the predicted sequence (by using standard dynamic programming) and follows that optimum to serve actual requests.
• Opt is the optimum offline algorithm executed on the actual sequence. This optimum is computed by using the same dynamic programming as in the implementation of Predict.
• Online is state-of-the-art online randomized algorithm for page migration that achieves 2.62approximation in expectation. This algorithm is described in Section 4.1 of Westbrook (1994).
Since it is randomized, on each input we perform 100 runs of Online and as the output report the average of all the runs. The standard deviation is smaller than 5%.
For both data sets, we depict the costs of the three algorithms as a function of either D or σ. See the text above each plots for the specification.
The results for the Brownian motion data set are depicted in Fig. 3. The top two figures show the cost incurred by each algorithm for fixed values of σ and As the value of σ increases, their costs starts to diverge. Nevertheless, the benefit of predictions is clear, as the cost of Predict is significantly lower than the cost of Online. Interestingly, this holds even though the fraction of requests predicted exactly is very close to 0. Each point in the plots is obtained by averaging over 15 runs. The standard deviation are also depicted in the figures as vertical lines (in some cases the standard deviation is so small that it is not visible in the plots).
The results for the Line data set is depicted in Fig. 6 (see Appendix C). They are qualitatively similar to those for Brownian motion.
More complex experiments. In Fig. 4 we present the results of a more complex experiment where we average 10 adversarial sequences, e.g., data observed in the past, and use it as a prediction for Predict. These adversarial sequences are obtained by perturbing the same ground truth. Notice that this means that in order to obtain a prediction we do not use the ground truth directly. Each point in Fig. 4 is obtained by averaging over 5 runs. The standard deviation is so small that it is not visible in the plot.
In this paper we studied online Page Migration, which is one of the classical online problems, in the setting where there is a predicted sequence of yet-to-be-seen requests. When this sequence predicts the online sequence reasonably well, our algorithm provides better approximation than state-of-the-art approach for classical online setting. It is an interesting open question to improve the constant in our competitive factor to obtain tight bounds.
Arguably the most interesting continuation of this work is to use ML tools to obtain the predicted sequence. For example, a neural network could be trained on the sequence seen so far to predict where the future requests will be. Combining this with our robust algorithm will likely give very strong results when the sequence has a somewhat predictable structure. Characterizing such predictable structures theoretically will likely yield new interesting models which has potentially application beyond Page Migration.
A.1.3 Combining the two cases.
We have concluded that in either case it holds A n -O n ≤ 4q(A n + O n ) and hence we derive
This concludes the analysis for uniform metric spaces.
A.2 General Metric Spaces -Theorem 2 (A)
As in uniform case, our goal for general metric spaces is to use Eq. ( 5) for proving the advertised competitive ratio. However, as we discussed in Section 3.1, the main challenge in applying Eq. ( 5) lies in upper-bounding the ratio between m((t i-1 , t i ]) and t i -t i-1 by a small constant, ideally much smaller than 1. Unfortunately, this ratio can be as large as 1 as OPT (or ALG) could possibly move on every single request. To see that, consider the scenario in which all the requests are on the x-axis and are requested in their increasing order of their location. Then, for all but potentially the last D requests, OPT would move from request to request. To bypass this behavior of OPT and ALG, we define and analyze their "lazy" variants, i.e., variants in which OPT and ALG are allowed to move only at the i-th request when i is a multiple of εD. We now state the algorithm.
We use the following algorithm ALG lazy : Compute the optimal offline solution (on ŝ) while only moving on multiples of εD. Let A lazy be the cost of the solution s and let A lazy be the cost of the solution on ŝ. Note that there can be better offline algorithms for ŝ, however ALG lazy has the minimal cost among all online algorithms that are only allowed to move every multiple of εD.
We also need to consider a lazy version of OPT, which we do in the following lemma. There we show that making any algorithm lazy does not increase the cost by more than a factor of (1 + ε). In particular, we will show O lazy ≤ (1 + ε)OPT. Let A lazy t and O lazy t denote their costs at time t. Lemma 4. Let ε ∈ (0, 1]. Consider an arbitrary prefix w of length t of a sequence of requests. Let B t be the cost of any algorithm ALG B serving w. Let B lazy t be the cost of the algorithm that has to move at every time step that is a multiple of εD (and is not allowed to move at any other time step), and to move to the position where ALG B is at that time step. Then, we have
Proof. Let x i be the distance of the i-th move and y i be the cost for serving the i-th request remotely. Then,
Now we relate B t and B lazy t . B lazy t has two components: the moving cost and the cost for serving remotely. By triangle inequality, the moving cost is upper-bounded by D i x i . Consider now interval I j ∈ [jεD +1, (j +1)εD] for some integer j. To serve point i ∈ I j remotely, the cost is, by triangle inequality, at most the cost of y i plus the cost of traversing all the points with indices in I j where ALG B has moved to. Thus the cost per request i ∈ I j is upper-bounded by y i + k∈Ij x k . Note that the summation k∈Ij x k is charged to εD requests. Hence, summing over all the intervals gives
Define O lazy as the cost of the optimal algorithm for s that is allowed to move only at time steps which are multiple of εD. Similarly as in Lemma 4, we have O lazy n ≤ (1 + ε)O n . Thus,
Now we need to upper-bound
. We will do that by showing that the same statements as we developed in Section 4.1 hold for A lazy and O lazy . To that end, observe that to derive Eq. ( 7) we used the fact that  ≤ Ô. Notice that the analog inequality A lazy ≤ lazy holds, since ALG lazy is the the optimal offline algorithm that only moves every multiple of εD.
Hence, we can obtain the derivation Eq. ( 11) for
Since for the lazy versions we have |t i -t i-1 | = εD, Assumption 1 implies m((t i-1 , t i ]) ≤ εqD. Plugging this into Eq. ( 16) gives
From Eq. ( 15) we establish
This concludes the proof of Theorem 2 (A).
So far we designed algorithms for the online page migration problem that have small competitive ratio when Assumption 1 holds. In this section we build on those algorithm and design a (robust) algorithm that performs well even when Assumption 1 does not hold, while still retaining competitiveness when Assumption 1 is true. We refer to this algorithm by ALG robust . For ALG robust we prove the following.
Theorem 5. Let γ be the competitive ratio of ALG for the online page migration problem, and let q be a positive number less than 1/24. If Assumption 1 holds, then ALG robust is γ • (1 + O(q))-competitive, and otherwise ALG robust is O(1/q)-competitive.
Using our techniques it is straight-forward to obtain an arbitrary trade-off between the two competitive ratios. Fix an arbitrary x ≥ 1, then Algorithm ALG robust is (1 + O(x • q))-competitive if Assumption 1 holds and O(1/(x • q))-competitive otherwise.
Let ALG online refer to an arbitrary online algorithm for the problem, e.g., Westbrook (1994). We now define ALG robust . This algorithm switches from ALG to ALG online when it detects that Assumption 1 does not hold. Instead of using ALG directly, we use a "lazy" version of ALG that works as follows. Follow the optimal offline solution given by ALG with a delay of 6qD steps. Let ALG lazy be the corresponding algorithm. (A lazy version for different setup of parameters was presented in Appendix A.2.)
Throughout its execution, ALG robust maintains/tracks in its memory the execution of ALG online on the prefix of s seen so far. That is, ALG robust maintains where ALG online would be at a given point in time in case a fallback is needed. Now ALG robust simply executes ALG lazy unless we find a violation of Assumption 1 is detected. Once such a violation is detected, the algorithm switches to ALG online by moving its location to ALG online 's current location. From there on ALG online is executed.
We now analyze ALG robust and show that in case Assumption 1 holds, then ALG and ALG robust are close in terms of total cost, and otherwise the cost of ALG robust is at most O(1/q) larger than that of ALG online .
B.1.1 Case 1: Assumption 1 holds for the entire sequence.
In this case ALG robust executes ALG lazy throughout. Following the same argument for ε = 6q as given for A lazy in the proof of Lemma 4, we have
Thus,
where we used the assumption that ALG is γ-competitive. This completes this case.
B.1.2 Case 2: Assumption 1 is violated at the t-th request.
Let t = t -qD + 1. Note that up to this point in time no violation occurred. We define the following: a is position of ALG lazy at time t ; a is the position of ALG online at time t + 1; o is the position of OPT at time t ; and, O p 0,t is the cost of OPT up to time t where we demand that OPT is at position p at t . In the following, we assume the following holds. We defer the proof of its correctness for later.
Intuitively, this means that we can bound the distance from the starting position by the cost of OPT.
Using Eq. ( 18), we get,
As O a 0,t and A lazy 0,t are at the same position at time t , inequality A lazy 0,t ≤ (1 + c 1 q)O a 0,t follows from Eq. ( 17) for a suitable constant c 1 . Note that O t ≥ D • d(p 0 , o), which holds since this cost is already incurred by moving to o, where we used triangle inequality.
Next, using triangle inequality again, we get
Furthermore, using Eq. ( 18), triangle inequality and a simple lower bound on A lazy 0,t as well as Eq. ( 20), we get,
Thus, plugging Eq. ( 21) and Eq. ( 20) into Eq. ( 19) and using A online ≤ O(O n ), we get
Thus, it only remains to prove Eq. ( 18), as we do using the following lemma. That lemma shows that if ALG moves its page to a location that is far from p 0 , then this means that there must be pages that are far from p 0 . Later we will show that OPT pays considerable cost to serve them, even if done remotely. See Fig. 5 for an illustration of the lemma. Lemma 6. Let P = p 1 , p 2 , . . . be the sequence of page locations that ALG produces. Let p max be the furthest point with respect to p 0 a page is moved to by the ALG, i.e., In case that there are several pages at p max , we let p max be the first among them. Let d max def = d(p max , p 0 ).
Let P be the maximal consecutive sequence of P including p max consisting of pages that are each at distance at least r def = d max /4 from p 0 . for q < 1/24, it holds that the page locations in P serve together at least 6qD points at distance r from p 0 in the oracle sequence. , where we argue that the reason we moved a page to a location far away (at distance max ) from p 0 means that there must be many points that are at least at distance r = d max /4 from p 0 . OPT will have to serve most of these points as well. The squares denote location of pages, the small circles denote page requests, the solid lines between squares and small circles depict a remotely served request. The dashed lines denote the movement of the page. The sequence P consists of p , p max and p .
Proof. The proof proceeds by contradiction. Suppose that P serves fewer than 6qD points in the oracle sequence. We will show that a better solution consists of replacing the sequence P by simply moving to p 0 and serving all points remotely from there. Since P is a maximal sequence of P including p max such that each page location is at distance r from p 0 , ALG moves by at least d max -r within P . Hence, the cost of ALG using the page locations P is at least
where the d i represents the distances to pages served remotely from the page locations in P (depicted as solid lines connected to p, p max and p in Fig. 5). Consider a request s that is served from location p in the original (using P ) solution. In the new solution, where all points are served from p 0 , serving any request has, by triangle inequality, a cost of at most d(p 0 , p) + d(p, s) ≤ d max + d(p, s). Moreover, observe that the sequence P consists of at most 6qD locations. This is because otherwise there would be a location that does not serve any points. Putting everything together, the cost of the new solution is at most
where the 2Dr accounts for moving the page from the location preceding P to p 0 (the cost of at most Dr) and moving the page from p 0 to the location just after P (also the cost of at most Dr). Recall that r = d max /4. Thus, Eq. ( 23) is cheaper than the solution Eq. ( 22) for q small enough (i.e., for q < 1/24), which contradicts the optimality of ALG of the oracle sequence.
By Lemma 6, we conclude that there are at least 6qD points at distance r from p 0 in the oracle sequence. Note that the final sequence s will contain at least 6qD -2qD of these points, due to our assumption on noise and the fact that up to the first violation of Assumption 1 were detected as time t. OPT has to serve these points as well and thus O t ≥ (6qD -2qD)r = 4qD • d max /4 ≥ qD • d(a, p 0 ), which yields Eq. ( 18) and therefore completes the proof.
Note that if each interval of length D has at most a fraction of q of errors, then it is also the case that each interval of length √ qD has at most a fraction of √ q of errors. Thus, if q tends to 0, the competitive ratio tends to 1 even if the interval length remains fixed.
We oversimplified here, since the right hand side of (1) only holds for the sum of all points, but a similar argument can be made for a single requests.