We consider online algorithms for the k-server problem on trees. Chrobak and Larmore proposed a k-competitive algorithm for this problem that has the optimal competitive ratio. However, a naive implementation of their algorithm has time complexity O(n) to process each request, where n is the number of nodes. We propose a new time-e cient implementation of this algorithm that has O(n log n) time complexity for preprocessing and O k2 + k log n time for processing a request. We also propose a quantum algorithm for the case where the nodes of the tree are presented using string paths. In this case, no preprocessing is needed, and the time complexity for each request is O(k2pn log n). When the number of requests is o on the total runtime compared to our classical algorithm.
Online optimization is a eld of optimization theory that deals with optimization
problems having no knowledge of the future [
In this paper, we focus on e cient online algorithms in terms of time
complexity. We consider the k-server problem on trees. Chrobak and Larmore [
We also revisit the problem of nding the rst marked element in a collection
of m objects. It is well-known that it can be solved in expected O(pm) queries
when given quantum oracle access to the input, and expected O(px) queires
where x is the position of the rst marked element [
We then consider the k-server problem in the case where the description of the tree is given by string paths. The string path of a node in a rooted tree is a sequence of length h, where h is the height of the node, describing the path from the root to the node. Such a way of representing the trees is useful, for example, as a path to a le in le systems. Assuming oracle access to the length of the string path of each node and to each element on the string path with time complexity O(1), we obtain a quantum algorithm for this problem with O(k2pn log(n)) running time to process each request and without preprocessing. This algorithm is based on our improved quantum search algorithm. When the number of requests is o
pk2n , the total runtime of our quantum algorithm is smaller than the classical one.
The structure of the paper is the following. Section 2 contains preliminaries. The classical algorithm is described in Section 3. Section 4 contains our improved quantum search algorithm. The quantum algorithm for the k-server problem is described in Section 5. 2 2.1
An online minimization problem consists of a set I of inputs and a cost function. Each input I = (x1; : : : ; xn) is a sequence of requests, where n is the length of the input jIj = n. Furthermore, a set of feasible outputs (or solutions) Oe(I) is associated with each I; an output is a sequence of answers O = (y1; : : : ; yn). The cost function assigns a positive real value cost(I; O) to I 2 I and O 2 Oe(I). An optimal solution for I 2 I is Oopt(I) = arg minO2Oe(I) cost(I; O).
Let us de ne an online algorithm for this problem. A deterministic online algorithm A computes the output sequence A(I) = (y1; : : : ; yn) such that yi is computed based on x1; : : : ; xi. We say that A is c-competitive if there exists a constant 0 such that, for every n and for any input I of size n, we have: cost(I; A(I)) c cost(I; OOpt(I)) + . The minimal c that satis es the previous condition is called the competitive ratio of A. 2.2
Consider a rooted tree G = (V; E), where V is the set of nodes/vertices, and E is the set of edges. Let n = jV j be the number of nodes, or equivalently the size of the tree. We denote by 1 the root of the tree. A path P is a sequence of nodes (v1; : : : ; vh) that are connected by edges, i.e. (vi; vi+1) 2 E for all i 2 f1; : : : ; h 1g, such that there are no duplicates among v1; : : : ; vh. Here h is a length of the path. Between any two nodes v and u on the tree, there is a unique path. The distance dist(v; u) is the length of this path. For each node v we can de ne a parent node Parent(v) which is the rst node on the unique path from v to root 1. We have dist (1; Parent(v))+1 = dist(1; v). Additionally, we can de ne the set of children Children(v) = fu : Parent(u) = vg. Any node y on the unique path from root 1 to node v is an ancestor of node v.
tree, the Lowest Common Ancestor is the node w such that w is an ancestor of both u and v, and w is the closest one to u and v among all such ancestors. The following result is well-known.
Lemma 1 ([
We call LCA Preprocessing() the subroutine that does the preprocessing for the algorithm and LCA(u; v) that computes the LCA of two nodes u and v.
Binary Lifting Technique. This technique from [
BL Preprocessing() prepares the required data structures. The time complexity is O(n log n).
MoveUp(v; z) returns a vertex v0 on the path from v to the root and at distance dist(v0; v) = z. The time complexity is O(log n).
The technique is well documented in the literature. We present an
implementation in the arxiv version [
k-server Problem on Trees Let G = (V; E) be a rooted tree, and we are given k servers that can move among nodes of G. At each time slot, a request q 2 V appears. We have to \serve" this request, that is, to choose one of the k servers and move it to q. The other servers are also allowed to move. The cost function is the distance by which we move the servers. In other words, if before the request, the servers are at positions v1; : : : ; vk and after the request they are at v10; : : : ; vk0, then q 2 fv10; : : : ; vk0g and the cost of the move is Pk
i=1 dist(vi; vi0). The cost of a sequence of requests is the sum of the costs of serving each requests. The problem is to design a strategy that minimizes the cost of servicing a sequence of requests given online. 2.4
We use the standard form of the quantum query model. Let f : D ! f0; 1g; D
f0; 1gm be an m variable function. We wish to compute on an input x 2 D.
We are given an oracle access to the input x, i.e. it is realized by a speci c
unitary transformation usually de ned as jii jzi jwi ! jii jz + xi (mod 2)i jwi
where the jii register indicates the index of the variable we are querying, jzi is the
output register, and jwi is some auxiliary work-space. An algorithm in the query
model consists of alternating applications of arbitrary unitaries independent of
the input and the query unitary, and a measurement in the end. The smallest
number of queries for an algorithm that outputs f (x) with probability 32 on
all x is called the quantum query complexity of the function f and is denoted by
Q(f ). We refer the readers to [
In search problems, one will try to minimize the number of queries to the
oracle. In the classical setting, one needs O(m) queries to solve such a problem.
Grover, on the other hand, constructed a quantum algorithm that solves the
search problem with only O(pm) queries [
A Fast Online Algorithm for k-server Problem on Trees
with Preprocessing
We rst describe Chrobak-Larmore's k-competitive algorithm for k-server
problem on trees from [
The naive implementation of this algorithm has time complexity O(n) for
each request. First, we run a depth- rst search with time labels [
In the following, we present an e ective implementation of Chrobak-Larmore's algorithm with preprocessing. The preprocessing part is done once and has O(n log n) time complexity (Theorem 1). The request processing part is done for each request and has O k2 + k log n time complexity (Theorem 2). 3.1
We do the following steps for the preprocessing :
1. We do required preprocessing for LCA algorithm (Section 2.2)
2. We do required preprocessing for Binary lifting technique (Section 2.2)
3. Additionally, for each vertex v we compute the distance from the root to v,
i.e. dist(1; v). This can be done using a depth- rst search algorithm [
Theorem 1. The preprocessing has time complexity O(n log n).
Proof. The time complexity of the preprocessing phase is O(n) for LCA, O(n log n) for the binary lifting technique and O(n) for ComputeDistance(1). Therefore, the total time complexity is O(n log n). Algorithm 1 Preprocessing. The preprocessing procedure.
LCA Preprocessing() BL Preprocessing() dist(1; 1) 0
ComputeDistance(1) 3.2
Assume that we have a request on a vertex q, and the servers are on the vertices v1; : : : ; vk. We do the following steps, implemented in Algorithms 2 and 4. Step 1. We sort all the servers by their distance to the node q. The distance dist(v; q) between a node v and the node q can be computed in the following way. Let l = LCA(v; q) be the lowest common ancestor of v and q, then dist(v; q) = dist(1; q) + dist(1; v) 2 dist(1; l). Using the prepocessing, this quantity can be computed in constant time. We denote by Sort(q; v1; : : : ; vk) this sorting procedure. In the following steps we assume that dist(vi; q) dist(vi+1; q) for i 2 f1; : : : ; k 1g.
Step 2. The rst server on v1 processes the request. We move it to the node q. Step 3. For i 2 f2; : : : kg we consider the server on vi. It will be inactive when some other server with a smaller index arrives on the path between vi and q. Section 3.3 contains the di erent cases that can happen and how to compute the distance d traveled by vi before it becomes inactive. We then move the i-th server d steps towards the request q. The new position of the i-th server is vi0. Algorithm 2 Request(q). Request processing procedure. minj<i diq;j.
When processing a request, all servers except one will eventually become inactive. The crucial part of the optimization is to compute when a server becomes inactive quickly. For the purpose of computing this time, we claim that we can pretend that servers \never go inactive". Formally, let q be a request, i be a server, and j another server with smaller index. We know that i will become inactive because it is not the closest to the target. However it is possible that this particular server j is not the one that will render i inactive. Nevertheless, we can pretend that j will never become inactive and compute the distance i will travel before going inactive because of j, call this distance diq;j (the index i is xed in this reasoning). We claim the following: Lemma 2. For any request q and server i > 1 ( i.e. a server that will become inactive), the distance Diq travelled by i before it becomes inactive is equal to
. see Algorithm 3 . see Algorithm 4 Proof. Let j0 be one of the servers that renders i inactive, then Diq = diq;j0 because j0 will not become inactive before it makes i inactive, hence for the purpose of computing Di, it makes no di erence whether j0 eventually becomes q inactive or not. Therefore, we only need to prove no other di;j is strictly smaller. Assume for contradiction that diq;j < Diq for some j < i, and pick j so that diq;j is minimum among all j < i (and in case of equality, pick j the smallest possible). q Then, it means there exists a vertex t such that di;j = dist(vj ; t) 6 dist(vi; t) and t is on the paths from vi and vj to q. Now we claim that j must become inactive before it reaches t. Indeed, if not, it would reach t and makes i inactive q q q after a distance di;j < D , which is impossible by de nition of D . Therefore, j is i i rendered inactive before reaching t by another server ` reaching some vertex u on the path from vj to t. In particular, we must have Djq = dist(v`; u) 6 dist(vj ; u) and dist(vj ; u) < dist(vj ; t). But now observe that if we pretend that ` never goes inactive, it will reach t after travelling a distance dist(v`; u) + dist(u; t) 6 dist(vj ; u) + dist(u; t) = dist(vj ; t) hence di;` = dist(v`; t) 6 dist(vj ; t) = diq;j . But q q q q we chose j so that di;j is minimal so we must have di;` = di;j and therefore, j < ` (we sort by index in case of tie). Going back to the computation, we see that q q di;` = di;j implies that dist(vi; u) = dist(v`; u), i.e. i and ` reach u at the same time. But when two servers reach the same vertex simultaneously, the greater index goes inactive, i.e. ` would go inactive because of j. This is a contradiction because we assumed that ` is the one making j inactive.
We have now reduced the problem to the following question: given a server i and another server j with smaller index, compute diq;j , the distance until i becomes inactive because of j, pretending that j never goes inactive. There are several cases to consider, depicted in Figure 1, depending on the relationship of vi, vj and q in the tree. Let t be the vertex where the paths from vi to q and vj q to q intersect the rst time, then di;j = dist(vj ; t) and 1. if q is an ancestor of vi and vj , then t = LCA(vi; vj ); 2. if q is an ancestor of vi but not of vj , then t = q; 3. if vi is an ancestor of q, then t = LCA(q; vj ) because vi must also be ancestor of vj since vj is closer to q than vi; 4. if the LCA of vj and q is not an ancestor of vi, then t = LCA(vj ; q); 5. if the LCA of vi and vj is not an ancestor of q, then t = LCA(vj ; vi); 6. otherwise t = LCA(vi; q).
Note that in this case distinction, the order of the cases is important: if cases 1 to 3 do not apply for example, then we know that vi is not an ancestor of q and q is not an ancestor of vi.
Lemma 3. DistanceToInactive has time complexity O (k).
Proof. Since a vertex u is ancestor of v if LCA(u; v) = u, we can check this condition in O(1) due to results from Section 2.2. It follows that we can compute q di;j for every i; j; q in O(1) and there are at most k other servers to consider. Algorithm 3 DistanceToInactive(q; i). Compute the distance travelled before going inactive.
d 1 for j 2 f1; : : : ; i 1g do t do case analysis as above d min(d; dist(t; vj)) return d vi vi vj case 4 t t case 1 q vj q vi vi q t case 2 vj vj q q vi t t case 3 case 5 case 6 vi vj q vj We now consider the following problem: given a server v and a distance z, how to e ciently compute the new position of the server after moving it z steps towards q. We use the binary lifting technique for this procedure.
Let l = LCA(v; q). If dist(l; v) z, then the result node is on the path between v and l. We can thus invoke MoveUp(v; z) from Section 2.2. Otherwise, we should move the server rst to l. We then move it z dist(l; v) steps down towards q from l. Moving down from l is the same as moving up dist(l; q) (z dist(l; v)) steps from q. The algorithm is presented in Algorithm 4. Algorithm 4 Move(v; z). Moves of a server from v to distance z on a path from v to q.
l = LCA(v; q) if z dist(l; v) then
Result MoveUp(v; z) if z > dist(l; v) then z z dist(l; v)
Result MoveUp(q; dist(l; q) return Result z) Lemma 4. The time complexity of Move is O (log n).
Proof. The time complexity of MoveUp is O(log n) using the binary lifting technique from Section 2.2 and LCA is in O(1) by Section 2.2. Furthermore, we can compute the distance between any two nodes in O(1) thanks to the preprocessing. Therefore, the total complexity is O(log n).
Theorem 2. The time complexity of the request processing phase is O k2 + k log n . Proof. The complexity of sorting the servers by distance is O(k log k). For each server, we compute the distance traveled before being inactive in O(1) by Lemma 3. We then move each server by that distance in time O(log n) by Lemma 4. Therefore, the complexity of processing one server is O(k + log n), and there are k servers. 4
Binary Search for a Function with Errors Consider a search space S = f1; : : : ; mg and a subset M S of marked elements. De ne the indicator function gM : S2 ! f0; 1g by gM (`; r) = 1 if f`; : : : ; rg \ M 6= ?; and 0 otherwise: In other words, gM (`; r) indicates whether there is a marked element from M in the interval [`; r]. Now assume that we do not know M but have access to a two-sided probabilistic approximation g~ of gM . Formally, there is a probability p < 1=2 such that for any `; r 2 S, g~(`; r) = gM (`; r) with probability at least 1 p and 1 gM (`; r) otherwise. Intuitively, g~ behaves like gM with probability at least 1 p. However, sometimes it makes mistakes and returns a completely wrong answer. Note that g~ has two-sided error: it can return 0 even if the interval [`; r] contains a marked element, but more importantly, it can also return 1 even though the interval does not contain any marked element. We further assume that a call to g~(`; r) takes time T (r `) where T is some nondecreasing function. Typically, we assume that T (m) = o(m), i.e. T is strictly better than a linear search.
We now consider the problem of nding the rst marked element in S, with probability at least, say, 1=2. A trivial algorithm is to perform a linear search in O(m) until g~ returns 1. If g~ had no errors, we could perform a binary search in O(T (m)). This does not work very well in the presence of errors because decisions made are irreversible, and errors accumulate quickly. Our observation is that if we modify the binary search to boost the success probability of certain calls to g~, we can still solve the problem in time in O (T (m)). 4.1
The idea is inspired by [
. search interval . depth of the search . repeat d times and take the majority d
mid d + 1 Algorithm 5 Binary search for a function with two-sided errors ` 1; r m + 1 d 1 while ` < r do mid b(` + r)=2c vl g~(`; mid) if vl = 0 then
` mid + 1 else
r them several times and taking the majority: by this we mean that we take the most common answer, and return an error in the case of a tie.
Proposition 1. Assume that T satis es T (m=k) = O(T (m)=k ) for some > 0 and every m and k, then with probability more than 0:5, Algorithm 5 returns the position of the rst marked element, or m + 1 if none exists. The running time is O(T (m)).
Proof. The correctness of the algorithm, when there are no errors, is clear. We need to argue about the complexity and error probability.
At the uth iteration of the loop, the algorithm considers a segment [`; r] of length at most m 2 (u 1). The complexity of g~(`; mid) is at most O(T (r `)) = O T (m 2 (u 1)) but we repeat it 2u times, so the total complexity of the uth iteration is O uT m 2 (u 1) . The number of iterations is at most log2 m. Hence, the total complexity is uuA = O
1 T (m) X 2 u=1 uu
! 2 (2
1)2 = O
T (m) = O (T (m)) :
Finally, we need to analyze the success probability of the algorithm: at the uth iteration, the algorithm will run each test 2u times and each test has a constant probability of failure p. Hence for the algorithm to fail at iteration u, at least half of the 2u runs must fail: this happens with probability at most 2uu pu 6 2uue u pu 6 (2ep)u; where e = exp(1). Hence, the probability that the log2 m algorithm fails is bounded by P (2ep)u 6 Pu1=1(2ep)u 6 1 2e2pep . By taking p u=1 small enough (say 2ep < 31 ), which is always possible by repeating the calls to g~ a constant number of times to boost the probability, we can ensure that the algorithm fails less than half of the time.
Remark 1. The condition T (m=k) = O(T (m)=k ) for some > 0 and every m and k is clearly satis ed by any function of the form T (m) = m log m log log m. 4.2
A particularly useful application of the previous section is for quantum search, particularly when g~ is a Grover-like search. Indeed, Grover's search can decide in O(pm) queries if a marked element exists in an array of size m, with a constant probability of error.
More precisely, assume that we have a function f : f1; : : : mg ! f0; 1g and the task is to nd the minimal x 2 f1; : : : ; mg such that f (x) = 1. If we let g~(`; r) = GROVER(`; r; f ) then g~ has query complexity T (m) = pm and fails with constant probability. Hence, we can apply Proposition 1 and obtain an algorithm to nd the rst marked element with query complexity T (m) = O(pm) and constant probability of error. In fact, note that we are not making use of Proposition 1 to its full strength because g~ really has one-sided error: it will never return 1 if there are no marked element. We will make use of this observation later.
Proposition 2. There is a quantum algorithm that nds the rst marked element in an array of size m in O(pm) queries and error probability < 0:5.
As observed above, we are not really using Proposition 1 to its full strength
because Grover's search has one-sided error. This suggests that there is room for
improvement. Suppose that we now only have access to a two-sided probabilistic
approximation f~ of f . In other words, f can now make mistakes: it can return 1
for an unmarked element or 0 for a marked element with some small probability.
Formally, f~(x) = f (x) with probability at least 1 p and 1 f (x) otherwise,
for some probability p < 1=2. We cannot apply Grover's search directly in this
case, but some variants have been developed that can handle bounded errors [
In quantum computing, f rarely has two-sided errors. For instance, Grover's search has a one-sided error only. If we assume that f~ has one-sided error only, we can obtain a slightly better version of Proposition 3. Formally, we assume that f~(x) = f (x) with probability at least 1 p and 0 otherwise.
Proposition 4. There exists a quantum algorithm that nds the rst marked
element in an array of size m in expected O(px) queries and with error
probability less than 0:5, where x is the position of the rst marked element, or O(pm)
queries if none is marked. Furthermore, it works even when the oracle access to
the array has one-sided error. Additionally, it has a worst-case query complexity
of O(pm) in all cases.
Proof. Let FindFirst denote the algorithm from Proposition 3 and GroverTwoSided
denote the variant of Grover's algorithm of [
r 1 . size of the search space while r n and GroverTwoSided(1; r; f~) = 0 do
r min(m; 2r) return FindFirst(r; f~)
We now show that this algorithm satis es the requirements of Proposition 4. To simplify the proof, we assume that the array always contains a marked element; this is without loss of generality because we can add an extra object at the end that is always marked. Furthermore, we assume that n is a power 2, this is again without loss of generality because we can add dummy object at the end at the cost of doubling the array size at most.
Recall that f~ has a one-sided error, and the same applies to GroverTwoSided in this case. Therefore the test GroverTwoSided(1; r; f~) = 0 can only fail if there actually is a marked element in the interval [1; r]. Of course, the problem is that it can succeed even though there is a marked element in this interval. Let p be the probability that this happens (i.e. GroverTwoSided fails), we know that this is < 1=2 by [17, Theorem 10]. Let x be the position of the rst marked element and let `x be such that 2`x 6 x < 2`x+1. Let R be the value of r after the loop, it is a random variable and always a power of 2. By the above reasoning, it is always the case that R > x. Furthermore, for any `x 6 ` < log2 n, the probability that R = 2` is at most p` `x (1 p). The call to FindFirst takes time O(pR) by Proposition 3. Hence, the expected time complexity of this algorithm is
O log n X p` `x (1 `=`x p)p2` ! = O = O = O px
1 p2`x X p`p2`
! p2`x `=0 1 1 p2p where we assume that p is small enough. This is always possible by repeating the calls to FindFirst a constant number of times to reduce the failure probability p. Finally, we note that the only way this algorithm can fail is if the (unique) call to FindFirst fails and this only happen with constant probability.
A Fast Quantum Implementation of Online Algorithm for k-server Problem on Trees We consider a special way of storing a rooted tree. Assume that for each vertex v we have access to a sequence av = (a1v; : : : ; avd) for d = dist(1; v) + 1. Here av is a path from the root (the vertex 1) to the vertex v, a1v = 1; avd = v. Such a way of describing a tree is not uncommon, for example when the tree represents a le system. A le path \c:nUsersnMyUsernnewdoc.txt" is exactly such a path in the le system tree. Here \c", \Users", \MyUser" are ancestors of \newdoc.txt", \c" is the root and \newdoc.txt" is the node itself.
We assume that we have access to the following two oracles in time O(1): (i) given a vertex u, a (classical) oracle that returns the length of the string path au; (ii) given a vertex u and an index i, a quantum oracle that returns the ith vertex aiu of the sequence au.
We can solve the k-server problem on trees using the same algorithm as in Section 3 with the following modi cations: (i) The function LCA(u; v) becomes LCP(au; av) where LCP(au; av) is a longest common pre x of two sequences au and av. (ii) MoveUp(v; z) is the vertex avd z where av is the sequence for v and d = javj; (iii) We can compute dist(u; v) if u is the ancestor of v: it is d0 d00, where d0 is a length of au and d00 is a length of av. Note that the invocations of dist in Algorithms 4 and 2 are always this form. The only exception is dist(u; v) in Sort in which the function uses LCA as a subroutine. The complexity of Sort is thus the same as the complexity of LCA or LCP in our case.
By doing so, we do not need any preprocessing. We now replace the LCP(au; av) function by a quantum subroutine QLCP(au; av), presented in Section 5.1, and keep everything else as is. This subroutine runs in time O(pn log n) with O n13 error probability. This allows us to obtain the following result.
Theorem 3. There is a quantum algorithm that processes a request in time O k2pn log n with probability of error O n1 . It does not require any preprocessing.
Proof. The complexity Move is the complexity of LCA that is QLCP in our implementation, plus the complexity of MoveUp. The former has complexity is O(pn log n) by Lemma 5, and the latter O(1) by the oracle. Therefore, the total running time of Move is O(pn log n).
The complexity of Request is O(k2) times the cost of LCA that is QLCP in our implementation, and then a call to Move. Additionally, the Sort function invokes LCA to compute distances. Hence, the complexity of Sort is O (k log k pn log n), and the total complexity is O k2pn log n .
We invoke, QLCP at most 4k2 times so the success probability is at least 1 n13 4k2 1 1 4n2 1 n1 for enough big n. Therefore, the error probability is O n1 .n3Note that we do not need any preprocessing.
. Repeat 3 log m times and take the majority vote 5.1
Let us consider the Longest Common Pre x (LCP) problem. Given two sequences (q1; : : : ; qd) and (b1; : : : ; bs), the problem is to nd t such that q1 = b1; : : : ; qt = bt and qi 6= bi for t + 1 i m, where m = min(d; s). Consider a function f : f1; : : : ; mg ! f0; 1g such that f (i) = 1 i qi 6= bi. Assume that x is the minimal argument such that f (x) = 1, then t = x 1. The LCP problem is equivalent to nding the rst marked element. It can be solved as follows. Algorithm 7 QLCP(q; b). Quantum algorithm for the longest common pre x. Lemma 5. Algorithm 7 nds the LCP of two sequences of length m in time O(pm log m) and with probability of error O
Proof. The correctness of the algorithm follows from the de nition of f . The complexity of FindFirst is O(pm) by Proposition 2. The total running time is O(pm log m) because of the repetitions.