On List Update and Work Function Algorithms

更新时间：2023-06-04 02:40:01 阅读量：实用文档文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

on是开还是关推荐度：
相关推荐

On List Update and Work Function AlgorithmsEric J. Anderson1, Kris Hildrum2, Anna R. Karlin1, April Rasala3, and Michael Saks41 Dept. of Computer Science, Univ. of Wash., feric,karling@cs.washington.edu 2 Computer Science Div., Univ. of Calif., Berkeley, hildrum@cs.berkeley.edu 3 Lab. of Computer Science, Mass. Inst. of Tech., arasala@theory.lcs.mit.edu 4 Dept. of Mathematics, Rutgers Univ., saks@math.rutgers.edu

Abstract. The list update problem, a well-studied problem in dynamic data structures, can be described abstractly as a metrical task system. In this paper, we prove that a generic metrical task system algorithm, called the work function algorithm, has constant competitive ratio for list update. In the process, we present a new formulation of the well-known\list factoring" technique in terms of a partial order on the elements of the list. This approach leads to a new simple proof that a large class of online algorithms, including Move-To-Front, is (2? 1=k)-competitive.

1 IntroductionThe list accessing or list update problem is one of the most well-studied problems in competitive analysis 1], 2], 3], 4], 5]. The problem consists of maintaining a set S of items in an unsorted linked list, for example as a data structure for implementation of a dictionary. The data structure must support three types of requests: ACCESS(x), INSERT(x) and DELETE(x), where x is the name, or\key", of an item stored in the list. We associate a cost with each of these operations as follows: accessing or deleting the i-th item on the list costs i; inserting a new item costs j+ 1 where j is the number of items currently on the list before insertion. We also allow the list to be reorganized, at a cost measured in terms of the minimum number of transpositions of consecutive items needed for the reorganization. We consider the standard cost model in the literature: immediately after an access or an insertion, the requested item may be moved at no extra cost to a position closer to the front of the list. These exchanges are called free exchanges. Intuitively, using free exchanges, the algorithm can lower the cost on subsequent requests. In addition, at any time, two adjacent items in the list can be exchanged at a cost of 1. These exchanges are called paid exchanges. The list update problem is to devise an algorithm for reorganizing the list, by performing free and/or paid exchanges, that minimizes search and reorganization costs. As usual, the algorithm will be evaluated in terms of its competitive ratio. As with much of the work on list accessing, we will focus on the static list update problem, where the list starts out with k elements in it, and all requests are

1.1 Motivation

2 accesses. The results described are easily extended to the dynamic case including insertions and deletions. Speci cally, the cost of an insertion is the same for any algorithm; and the cost of a deletion is the same as the cost of an access. Some results for static list update

are expressed in terms of the length k of the list. In the case of dynamic list update, the length k is no longer uniquely de ned. However, for constant-competitive ratio results, it is enough for our purposes to interpret k as the maximum length of the list where necessary. Many deterministic online algorithms have been proposed for the list update problem. Of these, perhaps the most well-known is the Move-To-Front algorithm: after accessing an item, move it to the front of the list, without changing 2 the relative order of the other items. Move-To-Front is known to be 2? k+1 competitive, and this is best possible 2], 7]. We note that other cost models have also been considered for the list update problem 6], 9], 10]. Increasing the cost of exchanges to two (instead of one) makes Move-To-Front optimal; this provides an independent proof that MoveTo-Front is two-competitive. Other alternatives analyzed in the literature include allowing free exchanges for other than the referenced element, and allowing free exchanges between elements that are not adjacent 9], 10]. These alternative cost models can lead to qualitatively di erent results.

1.2 Metrical task systemsThe (static) list update problem can also be considered within the metrical task system framework introduced by Borodin, Linial and Saks 8]. Metrical task systems (MTS) are an abstract model for online computation that captures a wide variety of online problems (paging, list update and the k-server problem, to name a few) as special cases. A metrical task system is a system with n states, with a distance function d de ned on the states: d(i; j ) is the distance between states i and j . The distances are assumed to form a metric. The MTS has a set T of allowable tasks; with each task 2 T is associated a vector ( (1); (2);:::; (n)) where (i) is the (nonnegative) cost of processing task in state i. An online algorithm is given a starting state and a sequence of tasks to be processed online, and must decide in which state to process each task. The goal of the algorithm is to minimize the total distance moved plus the total processing costs. The list update problem can be viewed as a metrical task system as follows. The states of the list update MTS are the k! possible orderings of the k elements in the list, which we also call list con gurations. There are k possible tasks, one corresponding to each list element x. The cost x ( ) of processing the task x in a particular list con guration, is equal to the depth of x in the list . The distance between two states or list con gurations is the number of inversions between the list orderings, considered as permutations.11 In this formulation,\free exchanges" are treated as made at unit cost immediately

before the item is referenced. Because the cost of these exchanges is precisely o set by the lower reference cost, this model is identical to the standard model. See 6],

3 One of the initial results about metrical task systems was that th

e work function algorithm (WFA) has competitive ratio 2n? 1 for all MTS's, where n is the number of states in the metrical task system 8]. It was also shown that this is best possible, in the sense that there exist metrical task systems for which no online algorithm can achieve a competitive ratio lower than 2n? 1. However, for many MTS's the upper bound of 2n? 1 is signi cantly higher than the best achievable competitive ratio. For example, there are known constant-competitive algorithms for list update, even though the MTS for a list of k elements has k! states. Another example is the k-server problem on a nite metric space?r consisting of r points. For this problem, the metrical task system has n= k states, but a celebrated result of Koutsoupias and Papadimitriou shows that in fact the very same work function algorithm is 2k? 1 competitive for this problem 12], nearly matching the known lower bound of k on the competitive ratio 13]. Unfortunately, our community understands very little at this point about how to design competitive algorithms that achieve close to the best possible competitive ratio for broad classes of metrical task systems. Indeed, one of the most intriguing open questions in this area is: For what metrical task systems is the work function algorithm strongly competitive? 2 Burley and Irani have shown the existence of metrical task systems for which the work function algorithm is not strongly competitive 14]. However, these\bad" metrical task systems seem to be rather contrived, and it is widely believed that the work function algorithm is in fact strongly competitive for large classes of natural metrical task systems. The desire to make progress towards answering this broad question is the foremost motivation for the work described in this paper. We were speci cally led to reconsider the list update problem when we observed the following curious fact: The Move-To-Front algorithm for list update is a work function algorithm. (Proposition 8, Section 4.) This observation was intriguing for two reasons. First because it raised the question of whether work function algorithms generally (that is, those with more general tie-breaking rules than that used in Move-To-Front ) are strongly competitive for list update. This would provide an example of a substantially di erent type of metrical task system for which the work function algorithm is strongly competitive than those considered in the past. The second and perhaps more exciting reason for studying work functions as they relate to list update is the tantalizing possibility that insight gained fromTheorem 1. We continue to use the term\paid exchanges" to describe speci cally those exchanges not involving the next-referenced element. 2 We say an algorithm is strongly competitive if its competitive ratio is within a constant factor of the best competitive ratio achievable.

4 that study could be helpful in the study of dynamic optimality for self-adjusting binary search tre

es 1], 15]. It is a long-standing open question whether or not there is a strongly competitive algorithm for dynamically rearranging a binary search tree using rotations, in response to a sequence of accesses. The similarity between Move-To-Front as an algorithm for dynamically rearranging linked lists, and the splay tree algorithm of Sleator and Tarjan 15] for dynamically rearranging binary search trees, long conjectured to be strongly competitive, is appealing. Our hope is that the use of work function-like algorithms might help to resolve this question for self-adjusting binary search trees.

1.3 ResultsThe main result of this paper is a proof that a class of work function algorithms is O(1) competitive for the list update problem.3 Proving this theorem requires getting a handle on the work function values, the optimal o ine costs of ending up in each state. This is tricky, as the o ine problem is very poorly understood. At present it is even unknown whether the problem of computing the optimal cost of executing a request sequence is NP-hard. The fastest optimal o -line algorithm currently known runs in time O(2k k!m), where k is the size of the list and m is the length of the request sequence 6]. Using the framework that we have developed for studying work functions and list update, we also present a new simple and illustrative proof that Move-ToFront and a large class of other online algorithms are (2? 1=k)-competitive. The rest of the paper is organized as follows. In Section 2, we present background material on work functions and on the work function algorithm. In Section 3, we present a formulation of the list update work functions in terms of a partial order on the elements of the list and use this formulation to prove that a large class of list update algorithms are (2? 1=k)-competitive. Finally, in Section 4 we present our main result, that work function algorithms are strongly competitive for list update.

2 BackgroundWe begin with background material on work functions and work function algorithms.

2.1 De nitionsConsider an arbitrary metrical task system, with states s 2 S and tasks 2 T . Given a sequence of requests, denote the t+ 1st request in the sequence as t+1 . Let t+1 be the task . Let (s) denote the cost of executing task in state s.3 The proof does not achieve the best possible competitive ratio of 2.

De nition 1. The work function !t(s) for any state s and index t is the lowest

cost of satisfying the rst t requests of and ending up in state s 16], 8]. Because the states and task costs are time-independent, the work functions can be calculated through a dynamic programming formulation (which can equally be taken as the de nition): !t+1(s0 )= min (!t (s)+ (s)+ d(s; s0 )): (1) s

The work function algorithm is de ned in terms of fundamental states: De nition 2. A state f is fundamental at time t if it satis es !t+1(f )= !t (f )+ (f ): (Where the context is evident, we will simply say a state f is\fundamen

tal".) The Work Function Algorithm (WFA), 16], 8], de ned for an arbitrary metrical task system, is the following: De nition 3. WFA: When in state st, service the request t+1= in the state st+1 such that st+1= argmins (!t+1 (s)+ d(st; s)) where the minimum is taken over states s that are fundamental at time t. From De nition 1, we see that the work function algorithm chooses st+1 so that st+1= argmins (!t (s)+ (s)+ d(st; s)): (2) We consider a variant of this work function algorithm, di ering only in the subscript of the work function: De nition 4. WFA0: When in state st, service the request in the state st+1 such that st+1= argmins (!t+1 (s)+ (s)+ d(st; s)): The minimum in this expression may not be unique. Accordingly, we de ne the class of states to which the work function algorithm might move: De nition 5. Given that WFA0 visits state st at time t, a state s at time t+ 1 is wfa-eligible if it is one of the states that minimizes the expression in De nition 4. We will see that, when applying WFA0 to list update, there always exists at least one wfa-eligible state that requires no paid exchanges (Proposition 8). In the remainder of the paper, we will assume that WFA0 chooses to move to a wfaeligible state of this type, i.e., one that can be reached by moving the referenced element only. We next note several elementary identities, which hold at all times t and all states s and s0 . As above, we let denote the t+ 1st task, and (s) its task cost in the state s.

2.2 Elementary identities Proposition 1.!t (s) !t (s0 )+ d(s; s0 ):Proof. For notational convenience, we show !t+1 (s) !t+1 (s0 )+ d(s; s0 ). From the de nition (Equation 1), there is some s for which !t+1 (s0 )= !t (~)+ (~)+~ s s d(~; s0 ). We know that !t (~)+ (~)+ d(~; s) is an upper bound on !t+1 (s) (by s s s s Equation 1). By the triangle inequality, d(~; s) d(~; s0 )+ d(s0; s). So we have s s !t+1 (s) !t+1 (s0 )+ d(s; s0 ). t u

Proposition 2.!t+1 (s) !t(s):Proof. By the alternative de nition above (Equation 1), for some s0 we have !t+1 (s)= !(s0 )+ d(s; s0 )+ (s0 ). By Proposition 1, !t (s) !(s0 )+ d(s; s0 ). Since all task costs are nonnegative, (s0 ) 0, and the result follows. t u

Proposition 3.!t+1 (s) !t (s)+ (s):Proof. By the de nition (Equation 1), !t+1 (s)= mins (!t (s0 )+ (s0 )+ d(s; s0 )), so for all such s0, !t+1 (s) !t (s0 )+ (s0 )+ d(s; s0 ). Substituting s for s0, and noting that d(s; s)= 0, the result follows. t u0

Proposition 4. For any s,!t+1 (s)= !t+1 (f )+ d(f; s)for some state f that is fundamental at time t. (The state s is derived from some fundamental state.) Proof. By the de nition (Equation 1), there is some f for which !t+1 (s)= !t (f )+ (f )+ d(f; s). We want to show that this f is fundamental. By Proposition 1, !t+1 (s) !t+1 (f )+ d(f; s); so !t (f )+ (f ) !t+1 (f ). But !t (f )+ (f ) !t+1 (f ) by Proposition 3. Hence !t(f )+ (f )= !t+1 (f ) and f is fundamental at time t. Then !t+1 (s)= !t+1

(f )+ d(f; s) by substitution. t u at time t, and suppose further that !t+1(s)= !t+1 (f )+ d(f; s) where f is fundamental. (There is at least one such state f by Proposition 4.) Then f is also wfa-eligible at time t, and x(f )= x(s). (The fundamental state f is wfa-eligible if s is.)

Proposition 5. Suppose WFA0 is in state st at time t. Suppose s is wfa-eligible

7Proof. Since s is wfa-eligible, it minimizes the expression in De nition 4, !t+1 (s)+ (s)+ d(st; s) !t+1 (s0 )+ (s0 )+ d(st; s0 ) for all s0 . If we show that !t+1 (f )+ (f )+ d(st; f ) !t+1 (s)+ (s)+ d(st; s), then f minimizes that expression as well, and f then must also be wfa-eligible. We observe rst that (f ) (s). By Propositions 2 and 3, !t+1 (s) !t (s)+ (s) !t (f )+ (s)+ d(f; s). Then (s)< (f ) would imply !t+1 (s)< !t (f )+ (f )+ d(f; s)= !t+1 (f )+ d(f; s). By hypothesis, however, we have !t+1 (f )+ d(f; s)= !t+1 (s). Next, by the triangle inequality, d(st; f ) d(st; s)+ d(f; s). Then !t+1 (f )+ d(st; f ) !t+1 (f )+ d(st; s)+ d(f; s)= !t+1 (s)+ d(st; s). Since (f ) (s), we have !t+1 (f )+ d(st; f )+ (f ) !t+1 (s)+ d(st; s)+ (s), and f is wfa-eligible. Finally, since s is also wfa-eligible, the above inequality cannot be strict. It would be if (f )< (s), so we must have (f )= (s). t u

Proposition 6. If s is wfa-eligible, then (s)

(st ).

Proof. Suppose instead that (s)> (st ). Then the condition for s to be wfaeligible (De nition 4) is !t+1 (s)+ (s)+ d(s; st )> !t+1 (s)+ (st )+ d(s; st ) !t+1 (st )+ (st ) by Proposition 1. But this last expression is De nition 4 applied to the state st . If st satis es De nition 4 strictly more strongly than s, s cannot be wfa-eligible. t u

2.3 ObservationsThe work function algorithm can be viewed as a compromise between two very natural algorithms. First, a natural greedy algorithm tries to minimize the cost spent on the current step. It services the (t+ 1)st request in a state s that minimizes d(st; s)+ (s): Another natural algorithm is a retrospective algorithm, which tries to match the state chosen by the optimal o ine algorithm. It services the (t+ 1)st request in a state s that minimizes !t+1 (s). Each of these natural algorithms is known to be noncompetitive for many metrical task systems. WFA combines these approaches and, interestingly, this results in an algorithm which is known to be strongly competitive for a number of problems for which neither the greedy and retrospective algorithms are competitive.4 The di erence between WFA and the variant, WFA0, is in the subscript of the work function. We actually feel that WFA0 is a slightly more natural algorithm, in light of the discussion above about combining a greedy approach and a retrospective approach. It is this latter work function algorithm WFA0 that we will focus on in this paper. It is fairly easy to extend our proof that WFA0 is O(1) competitive for list update to handle WFA as well. 54 Varying the relative weighting

of the greedy and retrospective components of the 5 In addition, many prior results which hold for

work function algorithm was explored in 17].

WFA also hold for WFA . For example, for the k-server problem the work function values at t and t+ 1 are identical0

3 A di erent view on list factoringA technique which has been used in the past to analyze list update algorithms is the list factoring technique, which reduces the competitive analysis of list accessing algorithms to lists of size two 3], 7], 18], 4], 19]. For example, this technique, in conjunction with phase partitioning, was used to prove that an algorithm called TimeStamp is 2-competitive 4], 19]. In this section, we repeat the development of this technique, but present it in a somewhat di erent way, in terms of a partial order on elements in the list.6 This view leads us to a simple generalization of previous results and will assist us in our study of WFA0 . Consider the metrical task system corresponding to a list of length two. In this case there are two lists, (a; b) (a in front of b) and (b; a) (b in front of a), and the distance between these two states is 1. Since for all t we have !t ((a; b))? 1 !t ((b; a)) !t((a; b))+1; we can characterize the work functions at any given time t as having one of three distinct properties: !t ((a; b))< !t ((b; a)), which we denote a b, !t ((a; b))= !t ((b; a)), which we denote a b, or !t ((a; b))> !t ((b; a)), which we denote a b. It is easy to verify directly from Equation (1) the transitions between these three properties as a result of references in the string .

?a b b

a a b

? 6b

a a b

Fig. 1. The three-state DFA: the state a

b corresponds to the case !t ((a; b))= !t ((b; a))? 1, the state a b corresponds to the case !t ((a; b))= !t ((b; a)), and the state a b corresponds to the case !t ((a; b))= !t ((b; a))+ 1The resulting three-state DFA shown in Figure 1 can be used to completely characterize the work functions, the optimal o ine list con guration, and the optimal cost to service a request sequence . The start state of the DFA is determined by the initial order of the elements in the list: it is a b if the for any states s that serve the t+ 1st request, !t+1 (s)= !t (s). Hence WFA and WFA de ne the same algorithm, and so WFA is 2k? 1 competitive for the k-server problem. The proof that WFA is 2n? 1 competitive for any metrical task system with n states also holds for WFA (using the same potential function), and so WFA also is 2n? 1 competitive for any metrical task system.0 0 0 0

6 This partial order has apparently been considered by Albers, von Stengel and

Werchner in the context of randomized list update, and was used as a basis for an optimal randomized online algorithm for lists of length 4. 20]

9 initial list is (a; b) and a b if the initial list is (b; a). Each successive request in results in a change of state in accordance with the transitions of the DFA, re ecting the work function

values after serving that request. Notice that the number of times a is referenced when in the state a b plus the number of times that b is referenced when in the state a b is equal to the total number of transitions into the middle DFA-state. The optimal sequence cannot avoid incurring cost upon such references. Therefore, the optimal cost of satisfying a sequence of requests is given by the number of transitions into the middle state of the DFA, plus the length of the sequence. The corresponding optimal o ine strategy is: Immediately before two or more references in a row to the same element, move that element to the front of the list. Now consider list update for a list of length k. The cost of an optimal sequence can be written as the sum of the number of exchanges performed 7 and the reference costs at each state. For any pair of elements (a; b) we can identify a pairwise reference cost attributable to (a; b), adding one whenever b is referenced but a is in front of b in the list, or vice versa. The standard list factoring approach is to describe the cost of any optimal sequence for satisfying by decomposing it into j j plus the sum over all pairs (a; b) of (i) this pairwise reference cost and (ii) all pairwise transpositions of a with b. For any pair (a; b), the sum of the pairwise transpositions and the pairwise reference cost describes a (possibly suboptimal) solution to the list of length two problem for the subsequence of consisting of references only to a and b. Therefore a lower bound on the optimal cost of satisfying is the sum of the costs of the optimal length-two solutions over all pairs (a; b), plus the length j j. It is important to note that this\list factoring" lower bound is not tight. Example 1. Consider a list of length ve, initialized abcde, and the reference sequence= ebddcceacde. The sum of the length-two solutions, plus the length of, is 31; the optimal cost of satisfying is 32. On the other hand, we do not know of any small examples where the optimal cost exceeds the list factoring lower bound by more than one, and we conjecture that the optimal cost does not exceed the lower bound by more than an additive constant related to the length of the list.

3.1 The partial order

We are thus led to consider the collection of k(k?1)=2 pairwise three-state DFAs, one for each pair a; b of elements in the list of length k. Consider the result of executing all these DFAs in parallel in response to requests in, starting from the states corresponding to the initial list. Figure 2 shows an example. Each DFA de nes a pairwise relation, a b, a b, or a b as the case may be, on the elements a and b. It is easy to verify that at every time t the resulting7 Recall that in our model we charge for each exchange, whether\paid" or\free"; each

free exchange in the standard model precisely corresponds in our model to a reduced reference cost on the immediately following reference. See 6], Theorem 1.

? x2? x3

x3?

? x2

x1?

? x3

x2 x2

? x1

? x3? x1

Fig. 2. Illustration of the evolution of the partial order on three elements in response

to the request sequence= x3; x2; x3; x2 assuming the initial list is ordered x1; x2; x3 from front to back. As usual, a directed edge from a to b indicates that a b in the partial order, whereas the absence of an edge indicates that a b

collection of relations de nes a valid partial order on the k elements of the list. In particular, the list con guration obtained by following Move-To-Front at every step is always consistent with this partial order. This partial order at each time t is de ned by the reference sequence, and does not depend on any choice of algorithm for list update. When we refer to the\partial order", we mean this partial order as induced by a particular at a given time t. When we say that an algorithm is\consistent with the partial order", we mean that, when applied to a reference sequence, the list con guration visited by the algorithm at each time t, considered as a total order of the list elements, is consistent with the partial order induced by at that time t. De ne by Gt (respectively It ) the number of elements greater than (respectively incomparable to) t in this partial order immediately prior to its reference at time t. By the discussion above, the optimal cost of servicing a request sequence of length n and ending up in any state s is bounded below by the number of transitions into middle states of the DFAs, which at each step t is Gt . P Hence for states s, !n (s) n+ 1 t n Gt: An easy counting argument also shows: Lemma 1. Pt It Pt Gt .Proof. Since we start with a total ordering on the elements, determined by the initial ordering of the list, each two element DFA begins either in state a b or a b. For each DFA, each transition out of its middle state a b must therefore be preceded by a transition into the middle state. Taken together, this implies that, cumulatively, the number of transitions out of middle states P cannot exceed the number of transitions into middle states. Since Gt is the P cumulative number of transitions into middle states of the DFA's, and It the cumulative number of transitions out of middle states, the result follows. t u

Lemma 1 leads to a useful characterization of online algorithms: Theorem 1. Any online list update algorithm that performs only free exchanges and maintains the invariant that the list order is consistent with the partial order is (2? 1=k)-competitive.

11Proof. Any online algorithm A that maintains a list order consistent with the partial order and performs no paid exchanges has a total cost A( ) satisfying P A( ) n+ t (It+ Gt ), where j j= n. ByP Lemma 1 and the fact that OPT ( ) kn, we can conclude that A( ) t u n+ 2 t Gt (2? 1=k)OPT ( ):

3.2 Competitive analysis of online algorithmsTheorem 1 provides a new, simple proof that a collection of online algorithms (many already known to be com

petitive) are all 2? 1=k competitive. These algorithms include Move-To-Front, TimeStamp, MRI (k), and SBR( ) 4], 5], 11]. Each of these online algorithms moves only the referenced element. By Theorem 1, it is enough to show that these algorithms maintain lists consistent with the partial order. We observed above that Move-To-Front maintains lists consistent with the partial order. Suppose the list is consistent with the partial order at time t, immediately before a reference to x. Then immediately after the reference (and after x is moved to the front), each element of the list is less than or incomparable to x, and is also behind x in the list. And because the respective pairwise order of other elements does not change, the list remains consistent with the partial order at time t+ 1. The TimeStamp algorithm (originally called TimeStamp (0)) due to Albers 4] is de ned as follows: On a request for an item x, insert x in front of the rst (from the front of the list) item y that precedes x on the list and was requested at most once since the last request for x. Do nothing if there is no such item y or if x is being requested for the rst time. The TimeStamp algorithm makes only free exchanges. Furthermore, by construction, after a reference to x, each item y that precedes it in the resulting list must have been requested at least twice since the last request for x. Therefore every element in front of x is incomparable to x (and not less than x) after the request. Each element behind x is less than or incomparable to x. Finally, the respective orders of other elements do not change as a result of the reference to x. Immediately prior to the initial reference to x, all elements in front of it are greater than it in the partial order. Hence TimeStamp{ and indeed any algorithm that moves x forward at least as far as TimeStamp does{ maintains a list order consistent with the partial order. Ran El-Yaniv has recently presented another family of algorithms, the MRI (k) family 5]: On a request for an item x, move x forward to just behind the rearmost item y that precedes x on the list and was requested at least k+ 1 times since the last request for x. If there is no such item y or if x is being requested for the rst time, move x to the front.

12 El-Yaniv shows that MRI (1) is equivalent (except for the rst move of each element) to TimeStamp. Because any element that is requested more than twice since the last reference to x must be incomparable to x after the reference to x, the result follows for all k. Schulz has recently presented the SBR( ) family 11]. From his Lemma 1 and the de nition, the referenced element is moved forward at least as far as TimeStamp. As shown above, any such algorithm maintains a list order consistent with the partial order. We have shown:

Corollary 1. Move-To-Front, TimeStamp, RTS and SBR( ) are all (2?1=k)competitive.

4 On the performance of work function algorithms4.1 PreliminariesWe begin with some de nitions and fa

cts. In what follows, the (t+ 1)st request t+1 is x. The task cost (s) is denoted x(s), which is the depth of x in the list con guration s. As before, we denote by st the state visited by the work function algorithm at time t, immediately before servicing the request to x.8 We rst de ne the"x binary relation on two states.

s by moving x forward while leaving the relative positions of other elementsundisturbed.

De nition 6. s"x s0 i s and s0 are identical, or if s0 can be derived from

Where x is understood from context, we write simply s" s0 .

Proposition 7. Suppose s is wfa-eligible, and s"x s0. Then !t+1(s) !t+1(s0).

(Moving x forward cannot increase the work function.) Furthermore, s0 is wfaeligible, and !t+1 (s)= !t+1 (s0 ). Proof. In the case of list update, the\free exchange" cost model implies that whenever s"x s0, x(s)= x(s0 )+ d(s; s0 ). Suppose rst that s is fundamental, !t+1 (s)= !t (s)+ x(s). We have !t+1 (s0 ) !t (s0 )+ x(s0 ) by Proposition 3, and !t (s0 ) !t(s)+ d(s0; s) by Proposition 1, so !t+1 (s0 ) !t (s)+ d(s0; s)+ x(s0 ). But d(s0; s)+ x(s0 )= x(s) so !t+1(s0 ) !t(s)+ x(s)= !t+1 (s) as was to be shown. Next suppose that s is wfa-eligible. By Proposition 1, we have !t+1 (s)= !t+1 (f )+ d(f; s) for some fundamental state f, for which also x(f )= x(s). This means that !t+1 (s)= !t (f )+ d(f; s)+ x(f )= !t (f )+ d(f; s)+ x(s): But 8 Again, we do not distinguish between a reference to x followed by free exchanges, on the one hand, and\paid" exchanges moving x forward, followed by a lower-cost reference to x, on the other. We refer to either of these combined steps as\servicing" the request to x.

!t+1 (s0 ) !t (s0 )+ x(s0 ) !t (f )+ d(f; s0 )+ x(s0 ) !t (f )+ d(f; s)+ d(s; s0 )+ x(s0 )= !t (f )+ d(f; s)+ x(s), so !t+1 (s0 ) !t+1 (s). Since d(s0; st ) d(s0; s)+ d(s; st ), we also have !t+1 (s0 )+ (s0 )+ d(s0; st ) !t+1 (s)+ (s)+ d(s; st ). This means that s0 is wfa-eligible. And if the inequality !t+1 (s0 ) !t+1 (s). were strict, s could not be wfa-eligible; so we have speci cally !t+1 (s0 )= !t+1 (s). t uRecall from Proposition 6 that (s) (st ), so the work function algorithm cannot move x backward. We can now show that (a) there always exists a wfa-eligible state that requires no paid exchanges, and (b) that if WFA0 is restricted to moving the referenced element only, it is equivalent to the following algorithm (\Move-To-Min-!"):

Mtm!: On a reference to x, move x forward (or not at all) to a state with lowest work function value immediately after the reference.In other words, if st is the state the algorithm is in immediately before servicing the t+ 1-st request t+1, then Mtm! moves to a state st+1 such that st+1= argmins: s" s !t+1 (s) and satis es t+1 there. Summarizing:t x

cial case of Mtm!.

Proposition 8. Mtm! is a special case of WFA0 and Move-To-Front is a spe-

Proof. We rst show that Mtm! is a special case of WFA0 . That is, we need to show that a

ny state produced by Mtm! is wfa-eligible. Suppose s is such a state for which st" s, and s minimizes !t+1 (s) among all such. Let s0 be some wfaeligible state for which st" s0 . (The existence of such a state is demonstrated below.) Then either s0" s or s" s0 . If the former, Proposition 7 applies and s is wfa-eligible. If the latter, d(s; s0 )= (x(s)? x(s0 )) and !t+1 (s) !t+1 (s0 ) together imply that !t+1 (s)+ x(s)+ d(st; s) !t+1 (s0 )+ x(s0 )+ d(st; s0 ), and again s is wfa-eligible. It remains to demonstrate that there is at least one wfa-eligible state s for which st" s. For convenience in what follows, we denote generally by s the state^ formed from s by moving x to the front without changing the order of other elements, s"x s and x(^)= 1. We show that the move-to-front state st, the^ s^ state which simultaneously satis es st" st and x(st )= 1, is wfa-eligible. By^^ Proposition 7, there must be some r wfa-eligible for which x(r)= 1 (for any^ wfa-eligible r0, take r0 ). It is a basic fact of permutation distance that d(r; st )= d(r; st )+ d(st; st ), because the interchanges in d(r; st ) not involving x can all be^^ resolved rst, without moving x. Given this fact, then !t+1 (r)+ x(r)+ d(r; st )= !t+1 (r)+ x(st )+ d(r; st )+ d(st; st ). But !t+1 (r)+ d(r; st ) !t+1 (st ) by Propo^^^^^ sition 1, hence !t+1 (st )+ x(st )+ d(st; st ) !t+1 (r)+ x(r)+ d(st; r), which was^^^ to be proved. As a corollary, the move-to-front algorithm Move-To-Front is a special case of the work function algorithm. t u

4.2 WFA is O(1) competitive for list update.0

In the preceding section, we characterized the work function algorithm in terms of the work function values of states formed by moving the referenced element forward. We noted that the work function value cannot increase as the referenced element is moved forward. In order to prove results about the work function algorithm, however, we must characterize all states to which the work function algorithm could move; and thus we must characterize circumstances under which the work function value must strictly decrease. Our proof technique, then, supposes by hypothesis that the work function algorithm encounters a state of a particular undesired type; we consider the optimal sequence of interchanges and references that leads to the given work function value; then we must construct a new sequence, leading to a state identical to the rst but for moving the referenced element forward, for which the total cost (of references and interchanges) is strictly lower. The technically challenging part of the proof is the following lemma.

Lemma 2. Consider= 1; x; 2; x, where in 2 there are no references to x, and j j= t. Let S be any fundamental state at the nal time step t. Let N be the set of elements that are not referenced in 2 that are in front of x in S, and let R be the set of elements (not including x) that are referenced^ in 2 . Also, let S be S with x m

oved forward just in front of the element in Nclosest to the front of the list. Then^ !t (S ) !t (S )+ jRj? jNj:

(3)

Proof. Suppose O is an optimal sequence ending in S after satisfying 1; x; 2; x, so that the cost of O is the work function value !t(S ). Let T denote the state in which O satis es the penultimate reference to x (between 1 and 2 ). We note that, at the point immediately prior to the penultimate reference to x (at time k, say), the cost of O is !k?1 (T ). In this construction, we modify O between T^^^ and S so as to obtain the state S, with S"x S and !t (S ) !t (S )? jNj+ jRj. Let N denote the total number of elements not referenced between k= x and t= x. (This set speci cally includes x, and is potentially much larger than jNj, which is the number of such elements in front of x in S .) Label these nonreferenced elements p1;:::; pN in the order they occur in the state T, with p1 referring to the one such closest to the front of the list. Denote by I X; Y] the number of interchanges of non-referenced elements (other than x) in a given sequence between the states X and Y .^ The construction of the lower-cost state S proceeds in three stages (see below for a diagram): 1. Rearrange the respective order of the non-referenced elements within T to obtain some state T 0. In T 0, x will occupy the location of the front-most nonreferenced element in T . All other non-referenced elements p in T 0 will satisfy a non-decreasing depth property, that p(T ) p(T 0).9 All referenced elements 9 Recall that we denote the depth of an element p in the state X by p(X ).

15 remain at their original depths. (The speci c de nition of the state T 0 will emerge from the rest of the construction; the cost of the modi ed sequence can be bounded by using only the non-decreasing depth property.) Evaluate k= x in this state T 0 . Using the non-decreasing depth property, we show (Proposition 9, proof deferred to the Appendix) that x(T 0 )+ d(T; T 0 ) x(T )+ jRj+ I T; T 0] (where I X; Y] is de ned as above). 2. Considering O as a sequence of transpositions and references transforming T to S, O: T ! S, apply a suitably chosen subsequence O0, including all of the references and many of the transpositions, of O. This subsequence O0 will transform T 0 to a state S 0 . In this state S 0, (i) each referenced element has the same depth as it does in S; (ii) the element x occupies the position of the frontmost non-referenced element in S; and (iii) all other non-referenced elements in S 0 are in their same respective pairwise order as in S . Evaluate x in S 0 . We show (Proposition 11, proof deferred to the Appendix) that such a transformation from some T 0 with the non-decreasing depth property, to S 0 as so de ned, can be achieved by a suitably chosen subsequence of O. We also show that I T; T 0]+ I T 0; S 0] I T; S], by showing that the interchanges between non-referenced items in the transformations from T to T 0 and from T 0 to

S 0 are all contained in O.^^^ 3. Transform S 0 to the state S, where S is de ned by (i) S"x S, and (ii)^ is the depth of the front-most non-referenced element in S the depth of x in S (which is also its depth in S 0 ). We show (Proposition 10, proof deferred to the Appendix) that x(S 0 )+^ d(S 0; S )+ jNj x(S ). This process can be illustrated as follows, using ! to denote a reference, and; to denote pairwise interchanges between references. The original sequence O has: x x

:::; T?! T;:::; S?! S (Recall that we assume that O satis es x= t in S .)

After the above modi cations (denoted 1, 2, 3), the sequence is:3^ x x 2 O 1:::; T; T 0?! T 0:::; S 0?! S 0; S

The result now follows by comparing the cost of the modi ed sequence to the cost of the original sequence from and after !k?1 (T ). The cost attributable to the original sequence is the sum of 1. x(T ); 2. the cost of references in 2; 3. from T to S, the cost of interchanges between referenced elements; 4. from T to S, the cost of interchanges between a referenced and a nonreferenced element; 5. from T to S, the cost I T; S] of interchanges between non-referenced elements; and 6. x(S ).

16 The cost attributable to the modi ed sequence O0 is the sum of 1. from T to T 0, the cost of all interchanges; 2. x(T 0 ); 3. the cost of references in 2; 4. from T 0 to S 0, the cost of interchanges between referenced elements; 5. from T 0 to S 0, the cost of interchanges between a referenced and a nonreferenced element; 6. from T 0 to S 0, the cost I T 0; S 0] of interchanges between non-referenced elements; 7. x(S 0 ); and^ 8. from S 0 to S, the cost of all interchanges. By construction, items two, three and four for the sequence O are identical to items three, four and ve for the sequence O0 . Thus we compare x(T )+ I T; S]+^ x(S ) for the rst sequence to d(T; T 0)+ x(T 0 )+ I T 0; S 0]+ x(S 0 )+ d(S 0; S ) for the second sequence. Given x(T 0 )+ d(T; T 0 ) x(T )+ jRj+ I T; T 0] (Proposition 9), I T; T 0]+^ I T 0; S 0] I T; S] (Proposition 11), and x(S 0 )+ d(S 0; S )+ jNj x(S ) (Proposition 10), the result follows by substitution. t u We obtain the following corollary to Lemma 2. Corollary 2. Consider a request sequence where the last request (the t-th request in ) is to x. If s is wfa-eligible after executing, then the depth of x in s is at most 2jRj, where R is the set of elements that have been referenced since the penultimate reference to x. Proof. Let f be a fundamental state such that !t+1 (s)= !t+1 (f )+ d(f; s). By Proposition 5, f is also wfa-eligible and x(f )= x(s). Suppose x(s)> 2jRj. Then x(f )> 2jRj. Elements in front of x in f either have or have not been referenced since the penultimate reference to x; so x(f )> 2jRj implies jNj> jRj, where N is the set of elements in front of x in f that have not been referenced since the^ penultimate reference to x. Then by Lemma 2 there exists f^ with !t (f )< !t (f )

t u and f"x f^, contradicting the assumption that f is wfa-eligible. Finally, we use the lemma to obtain the main theorem. Theorem 2. WFA0 is O(1) competitive. Proof. Consider an arbitrary element x, and let= 0; x; 1; x; 2; x, where in 1 and 2 there are no references to x. Then by Lemma 2 the depth of x in the Mtm! state, immediately before the nal reference to x, is at most 2r1+ r2, where r1 is the number of distinct elements referenced in 1 and r2 is the number of distinct elements referenced in 2, not referenced in 1, that are moved in front of x at some point during the subsequence 2 . As usual, let G be the number of elements greater than x immediately before its nal reference and let I be the number of elements incomparable to x immediately before its nal reference. In addition, let L(0) be the number of elements

17 less than x immediately before its nal reference that were incomparable to x immediately before the penultimate reference to x. We have r1+r2 G+I+L(0). Denote by t1 the time of the penultimate reference to x, and by t2 the time of the nal reference. Since each element in L(0) at time t2 is incomparable to x at time t1, we have L(0)P It1 . That is, for any t2, there is some t1< t2 such t2 P P P that L(0)t2 It1 . Thus t L(0)t t Gt by the counting t It . But t It argument, Lemma 1. Summarizing, we have

WFA0 ( )2X

Therefore, Mtm! is at least 6-competitive. t u Note that, for list update, the algorithm WFA (without the subscript) can be less e ective than WFA0 . Consider the sequence= bbb for a two-element list (a; b). After the second reference to b, the list con guration (b; a) has strictly lower work function value. But WFA does not (necessarily) move to that state until after the third reference to b. However, as noted above it is possible (by expanding the construction of the DFA to more states) to extend the above proof of O(1)-competitiveness to WFA. It is fairly clear that the competitive ratios shown by our analyses of these algorithms are not tight. The above example shows that WFA, even without paid exchanges, is no better than 3-competitive.

(Gt+ It+ L(0)t ) 6

(2r1+ r2 ) 2(r1+ r2 )X

Gt 6OPT ( )

5 AcknowledgmentsWe gratefully acknowledge discussions with Susanne Albers, Ran El-Yaniv, Sandy Irani, and T.S. Jayram. This work was supported in part by NSF grant EIA-9870740 and BSF grant 96-00247 (Karlin), the CRA Distributed Mentor Project (Hildrum and Rasala), and an IBM Research Fellowship (Anderson).

References1. S. Albers and J. Westbrook. Self-organizing data structures. In Online Algorithms: The State of the Art, Fiat-Woeginger, Springer, 1998. 2. D.D. Sleator and R.E. Tarjan. Amortized e ciency of list update and paging rules. Communications of the ACM, 28:202{208, 1985. 3. J.L. Bentley and C. McGeoch. Amortized analysis of self-organizing sequential search heuristics. Communications of the ACM, 28(4):404{411, 1985. 4. S. Albers. Improved randomized on-line algorithms for the

list update problem. SIAM Journal on Computing, 27: 682{693, 1998. 5. R. El-Yaniv. There are in nitely many competitive-optimal online list accessing algorithms. Discussion paper from The Center for Rationality and Interactive Decision Making. Hebrew University.

186. N. Reingold and J. Westbrook. O -line algorithms for the list update problem. Information Processing Letters, 60(2):75{80, 1996. 7. S. Irani. Two results on the list update problem. Information Processing Letters, 38(6):301{306, 1991. 8. A. Borodin, N. Linial, and M. Saks. An optimal online algorithm for metrical task systems. Journal of the ACM, 52:46{52, 1985. 9. S. Roura and C. Martinez. On the competitiveness of the Move-to-front rule. Technical Report LSI-96-63-R, Technical University of Catalonia, 1997. 10. M. Chrobak and J. Noga. Competitive algorithms for multilevel caching and relaxed list update. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 1998. 11. F. Schulz. Two new families of list update algorithms. In Proceedings of 9th International Symposium, ISAAC, Vol. 1533 of Lecture Notes in Computer Science, pp. 99{ 108, 1998. 12. E. Koutsoupias and C. Papadimitriou. On the k-server conjecture. Journal of the ACM, 42(5): 971{983, September 1995. 13. M. Manasse, L. McGeoch and D.D. Sleator. Competitive algorithms for server problems. Journal of Algorithms, 11:208{230, 1990. 14. W. Burley and S. Irani. On algorithm design for metrical task systems. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms, 1995. 15. D.D. Sleator and R.E. Tarjan. Self-adjusting binary search trees. Journal of the ACM, 32: 652-686, 1985. 16. M. Chrobak, L. Larmore. The server problem and on-line games. In On-Line Algorithms, Proceedings of a DIMACS Workshop, Vol. 7 of DIMACS Series in Discrete Mathematics and Computer Science, pp. 11{ 64, 1991. 17. W.R. Burley. Traversing layered graphs using the work function algorithm. Journal of Algorithms, 20(3):479{511, 1996. 18. B. Teia. A lower bound for randomized list update algorithms. Information Processing Letters, 47:5{9, 1993. 19. S. Albers, B. von Stengel and R. Werchner. A combined BIT and TIMESTAMP algorithm for the list update problem. Information Processing Letters; 56: 135{ 139, 1995. 20. S. Albers. Private communication.

6 AppendixIn this Appendix, we address the proofs of the three propositions leading to Lemma 2. The most intricate part of the part of the construction is contained in Proposition 11; we save its proof for last.

Proposition 9. Suppose T 0 is derived from T, such that (i) all referenced ele-

ments p have p(T 0 )= p(T ), (ii) x occupies in T 0 the location of the front-most non-referenced element in T, and (iii) T 0 has the non-decreasing depth property, p(T 0) p(T ) for all p 6= x. Then the number of exchanges required to transform T to T 0 is bounded by (i) the number of interchanges involving x, plus (ii) the number of referenced elements, plus (iii) the number of interchanges involving non-refer

enced elements. In particular, the cost of the reference to x in T is equal to the cost of the reference in T 0, plus the number of interchanges involving x.

19Proof. If the rst non-referenced element in T is x itself, then in order to satisfy the non-decreasing depth property, p(T 0)= p(T ) for all non-referenced elements, and there is nothing to prove. Otherwise, denote by p1;:::; pN the nonreferenced elements in their order in T, with pz= x. We note that for i> z, the non-decreasing depth property requires pi (T )= pi (T 0 ). We start by moving x forward to the location of the rst non-referenced element, p1 . These interchanges all involve x. Next, we move p1 to location 2.10 By the non-decreasing depth property, either p1 or p2 must occupy location 2. If p2 is x, we are done. Otherwise, there may be one interchange, between p1 and p2 . Inductively, at step i, for location i, each referenced element below location i has interchanged with at most one non-referenced element, and each referenced element above location i has not interchanged with any non-referenced elements; and some element pj; j< i, is either (i) adjacent to pi, or (ii) is in location i and pi is x. If the latter, we are done. If the former, one or the other of pi and pj must occupy location i by the non-decreasing depth property; swap them if necessary; and interchange the other with all referenced elements between location i and location i+ 1. By induction, each referenced element has interchanged with at most one non-referenced element, so the number of such interchanges is bounded by the number of referenced elements. The result follows. t u

We next prove Proposition 10, which is in some sense the obverse of the preceding one. Here x is already ahead of all other non-referenced elements; we move the non-referenced elements forward to their ending positions.

Proposition 10. As above, let S 0 be derived from the state S as follows:{ All referenced elements are in the same locations and in the same order in S 0 as in S .{ x occupies in S 0 the position of the front-most non-referenced element in S .{ All other non-referenced elements are in the same pairwise order in S 0 as in^ As above, let S be derived from the state S by moving x forward to immediately in front of the front-most non-referenced element. Then the cost x(S 0 ) of the^^ reference to x in state S 0, plus the distance d(S 0; S ) from S 0 to S, is less than the depth x(S ) of x in S by at least the number of non-referenced elements in front of x in S . That is, we have^ x(S 0 )+ d(S 0; S )+ jNj x(S ):Proof. Suppose x occupies the i0th non-referenced location from the front in S . (That is, jNj= i.) Denote the rst i non-referenced elements of S in order by q1;:::; qi= x. In S 0, the element qi?1 occupies position i; qi?2, position i? 1; and so on; q1 occupies position 2; and x occupies position 1. We transform^ S 0 to S by interchanging, for all 1< j< i, qj with all ref

erenced elements 10 In what follows, by slight abuse of notation, we refer to the location of the i th non-referenced element in T by the description\location i" or\position i".0

20 between it and qj?1, and q1 with all referenced elements between it and x. Each referenced element between x and qi?1 interchanges with at most one nonreferenced element, and each such is in front of x in S . Thus the number of^ exchanges required to transform S 0 to S, plus the number of referenced elements 0, plus the number of non-referenced elements in front of x in in front of x in S S, is no greater than the depth of x in S . The result follows. t u Finally, we address the most intricate part of the construction: Proposition 11. Suppose S 0 is derived from S, such that (i) all referenced elements p have p(S 0 )= p(S ), (ii) x occupies in S 0 the position of the front-most non-referenced element in S, and (iii) all other non-referenced elements are in their same respective order in S 0 as in S . Then there is a T 0 with the nondecreasing depth property, and a subsequence O0 O, such that (i) O0 (T 0)= S 0, and (ii) the cost of O is at least the cost of O0 plus the cost of interchanges I T 0; T] of non-referenced elements (other than x) necessary to derive T 0 from T. Proof. As above, we denote by pi the non-referenced element occupying the i0 th non-referenced position in T . For convenience, let z denote the location of x as a non-referenced element in T, pz= x.11 We proceed by iteratively constructing T 0 from the end of the list, beginning with O?1 (S 0 ). The location of referenced elements remains xed throughout the construction. As a result, we consider only the N positions of non-referenced elements. For convenience, we describe the iteration as proceeding from i= N to i= 1. (The\base case" is denoted by\i= N+ 1".) At each step, then, we de ne a map Oi: Ti0 ! S 0 . The non-decreasing depth property is maintained for the elements (other than x) in Oi?1 (S 0 )= Ti0 that occupy the locations i through N in Ti0. We show that any necessary interchanges of elements as we proceed from Ti0 to Ti0?1 correspond to transpositions in Oi0 . For each pair of elements p; q 6= x at locations i and below in Ti0, we can determine whether these two elements are in the same or in the opposite order in T . We denote by Ii Ti0; T] the number of pairwise inversions of such elements (other than x). We denote by jOj (respectively, jOi j) the number of transpositions in the sequence O (respectively, Oi ). Formally, we show by induction that for each i: 1. Oi (Ti0 )= S 0 (and Oi?1: S 0 ! Ti0 ) 2. Oi O in the sense of a subsequence of transpositions, and jOj jOi j+ Ii Ti0; T] (all swaps and inversions are accounted for) 3. x(Ti0 ) pi (T ) (x is no deeper than position i) 4. 8p 6= x with p(T ) pi (T ); p(Ti0) p(T ) (all elements other than x at position i or below in T have the non-decreasing depth property) 5. 8p; q 6= x with p(T ); q(T )< pi (T )

: (a) p(S )< x(S ) () p(Ti0) 6= p(T ), and p(S )> x(S ) () p(Ti0)= p(T )positions of non-referenced elements in T .

11 We use the terms\position" and\location" interchangeably to refer to the respective

21 (b) p(T )= q(Ti0 )=) p(S )> q(S ) To carry out the induction proof, we will start by demonstrating the hypotheses for an appropriate base case. For the induction step, we assume the ve hypotheses for i+ 1, derive a transformation Oi, and show the validity of the hypotheses for i. Then we de ne T 0= T1, and note that the non-increasing depth property is satis ed for all pi 6= x. We de ne O0= O1, and note all of the inversions between non-referenced elements in T 0 have been accounted for, i.e., I T; T 0]+ jO0 j jOj: Finally, we repeat that because the only transpositions removed from O are between non-referenced elements, the depths, and thus the reference costs, of all referenced elements remains identical between O and O0 .The base case. For the base case, we de ne Ob= O; Tb0= O?1 (T 0). (Notationally, b is N+ 1.) Then (1) and (2) follow from our de nition (Ib is zero). Items (3) and (4) are vacuous. We must show that items (5)(a) and (5)(b) are true for all non-referenced elements in Tb0. For item (5)(a), by construction of S 0, elements q deeper than x in S are una ected by the shift, q(S )> x(S )=) q(S )= q(S 0 ) so q(T )= q(Tb0 ), while elements q closer to the front of S are\shifted down", q(S )< x(S )=) q(S 0 ) 6= q(S ) (indeed q(S 0 )> q(S )), so q(T ) 6= q(Tb0 ). Finally, for (5)(b), p(T )= q(Tb0 ); p 6= q implies p(T ) 6= p(Tb0) implies (by (5)(a)) p(S )< x(S ), similarly q(S )< x(S ). By construction, p(S 0 )> p(S ) by one non-referenced position, but q(S 0 )= p(S ) since O?1 takes q to location p(T ) in Tb0. Hence p(S 0 )> q(S 0 ). Induction step. Now suppose the entire hypothesis is true for i+ 1 (including for example b= N+ 1). We will construct an appropriate mapping Oi that satis es the hypotheses for i. We describe three stages, depending on whether the element x has yet been considered. Denoting by z the location of x in T, so that x= pz, we consider pi for (i) i> z, (ii) i= z, (iii) i< z in turn. Case (i): i> z . We have the non-decreasing depth property for j 2 i+1;:::; N, which because i> z requires strictly that pj (Ti0+1 )= pj (T ) for all locations j . In this case, the non-decreasing depth property applied to i will require strictly that pi (T )= pi (T 0). Throughout this stage, in particular, the non-decreasing depth property for i implies Ii Ti0; T]= 0. We examine the current occupant of position i in Ti0+1 . There are three possibilities to consider:{ The occupant is pi itself, pi(Ti0+1 )= pi(T ). In that case, set Oi= Oi+1 . The non-decreasing depth property is (precisely) satis ed. Hypotheses (1) and (2) follow immediately from their validity for i+ 1; hypothesis (3) and (4) follow from the depth property; and hypothesis (5) is more restrictive, hence va

lid.{ The occupant is x, x(Ti0+1 )= pi (T ). In this case, Ti0 will be obtained by interchanging pi with x. We observe that pi (Ti0+1 )< x(Ti0+1 ) (by the depth property at i+ 1), and x(S 0 )< pi (S 0 ) by construction (x is the front-most non-referenced element in S 0 ), so x and pi are inverted by Oi+1, and there

本文来源：https://www.bwwdw.com/article/hdn1.html

相关文章：

化妆品网络广告策划书05-03

2011中考数学总复习（教师版）(1)01-05

研究生英语系列教程多维教程探索课后答案05-29

内蒙古自治区医师定期考核业务水平测评考试题库 (1)04-08

鳞状细胞癌相关抗原在肺部恶性和良性疾病中的变化07-17

外汇储备与消费者物价指数关联性分析12-26

鸣沙山作文600字06-30

我设计的云作文400字06-17

【两性同居指南】同居是性还是爱(1)03-29

上一篇：四年级数学上册家庭作业下一篇：250AYS80型离心油泵型号结构图,AY型离心油泵工作原理,三昌泵业