71:
the elements. If quicksort chooses the pivot in some deterministic fashion (for instance, always choosing the first element in the list), then it is easy for an adversary to arrange the data beforehand so that quicksort will perform in worst-case time. If, however, quicksort chooses some random element to be the pivot, then an adversary without knowledge of what random numbers are coming up cannot arrange the data to guarantee worst-case execution time for quicksort.
82:: Given a list of items and a sequence of requests for the various items, minimize the cost of accessing the list where the elements closer to the front of the list cost less to access. (Typically, the cost of accessing an item is equal to its position in the list.) After an access, the list may be rearranged. Most rearrangements have a cost. The
45:
For many algorithms, performance is dependent not only on the size of the inputs, but also on their values. For example, sorting an array of elements varies in difficulty depending on the initial order. Such data-dependent algorithms are analysed for average-case and worst-case data. Competitive
70:
algorithm chooses one element, called the "pivot", that is, on average, not too far from the center value of the data being sorted. Quicksort then separates the data into two piles, one of which contains all elements with value less than the value of the pivot, and the other containing the rest of
90:
swaps the accessed item with the item immediately before it, also at no cost. Classical methods of analysis showed that
Transpose is optimal in certain contexts. In practice, Move-To-Front performed much better. Competitive analysis was used to show that an adversary can make Transpose perform
94:
In the case of online requests from a server, competitive algorithms are used to overcome uncertainties about the future. That is, the algorithm does not "know" the future, while the imaginary adversary (the "competitor") "knows". Similarly, competitive algorithms were developed for distributed
62:
which has full knowledge of the algorithm's internal state at any point during its execution. (For a deterministic algorithm, there is no difference; either adversary can simply compute what state that algorithm must have at any time in the future, and choose difficult data accordingly.)
53:
In competitive analysis, one imagines an "adversary" which deliberately chooses difficult data, to maximize the ratio of the cost of the algorithm being studied and some optimal algorithm. When considering a randomized algorithm, one must further distinguish between an
42:, where the performance of an algorithm is measured only for "hard" inputs, competitive analysis requires that an algorithm perform well both on hard and easy inputs, where "hard" and "easy" are defined by the performance of the optimal offline algorithm.
26:, in which the performance of an online algorithm (which must satisfy an unpredictable sequence of requests, completing each request without being able to see the future) is compared to the performance of an optimal
95:
systems, where the algorithm has to react to a request arriving at one location, without "knowing" what has just happened in a remote location. This setting was presented in (
91:
arbitrarily badly compared to an optimal algorithm, whereas Move-To-Front can never be made to incur more than twice the cost of an optimal algorithm.
196:
218:
250:
108:
39:
255:
38:—the ratio between its performance and the offline algorithm's performance—is bounded. Unlike traditional
176:
47:
123:
79:
113:
58:, which has no knowledge of the random choices made by the algorithm pitted against it, and an
214:
192:
184:
157:
128:
118:
23:
141:
244:
206:
145:
229:
86:
simply moves the requested item to the front after the access, at no cost. The
172:
67:
171:
Aspnes, James (1998), "Competitive analysis of distributed algorithms", in
188:
183:, Lecture Notes in Computer Science, vol. 1442, pp. 118–146,
162:
74:
The classic on-line problem first analysed with competitive analysis (
30:
that can view the sequence of requests in advance. An algorithm is
148:(1985), "Amortized efficiency of list update and paging rules",
46:
analysis is a way of doing worst case analysis for on-line and
232:; Peleg, D. (1992), "Competitive Distributed Job Scheduling",
96:
75:
8:
211:Online Computation and Competitive Analysis
161:
181:Online Algorithms: The State of the Art
50:, which are typically data dependent.
16:Method for analyzing online algorithms
7:
22:is a method invented for analyzing
14:
97:Awerbuch, Kutten & Peleg 1992
234:ACM STOC, Victoria, BC, Canada
213:, Cambridge University Press,
1:
109:Adversary (online algorithm)
272:
150:Communications of the ACM
76:Sleator & Tarjan 1985
209:; El-Yaniv, R. (1998),
84:Move-To-Front algorithm
251:Analysis of algorithms
48:randomized algorithms
20:Competitive analysis
124:List update problem
88:Transpose algorithm
80:list update problem
56:oblivious adversary
40:worst-case analysis
189:10.1007/BFb0029567
114:Amortized analysis
60:adaptive adversary
256:Online algorithms
198:978-3-540-64917-5
163:10.1145/2786.2793
66:For example, the
36:competitive ratio
28:offline algorithm
24:online algorithms
263:
236:
223:
201:
177:Woeginger, G. J.
166:
165:
129:Online algorithm
119:K-server problem
271:
270:
266:
265:
264:
262:
261:
260:
241:
240:
227:
221:
205:
199:
170:
140:
137:
105:
17:
12:
11:
5:
269:
267:
259:
258:
253:
243:
242:
239:
238:
228:Awerbuch, B.;
225:
219:
203:
197:
168:
156:(2): 202–208,
136:
133:
132:
131:
126:
121:
116:
111:
104:
101:
15:
13:
10:
9:
6:
4:
3:
2:
268:
257:
254:
252:
249:
248:
246:
235:
231:
226:
222:
220:0-521-56392-5
216:
212:
208:
204:
200:
194:
190:
186:
182:
178:
174:
169:
164:
159:
155:
151:
147:
143:
139:
138:
134:
130:
127:
125:
122:
120:
117:
115:
112:
110:
107:
106:
102:
100:
98:
92:
89:
85:
81:
77:
72:
69:
64:
61:
57:
51:
49:
43:
41:
37:
33:
29:
25:
21:
233:
210:
180:
153:
149:
93:
87:
83:
73:
65:
59:
55:
52:
44:
35:
31:
27:
19:
18:
207:Borodin, A.
142:Sleator, D.
32:competitive
245:Categories
230:Kutten, S.
146:Tarjan, R.
135:References
78:) is the
68:quicksort
179:(eds.),
173:Fiat, A.
103:See also
34:if its
217:
195:
215:ISBN
193:ISBN
185:doi
158:doi
99:).
247::
191:,
175:;
154:28
152:,
144:;
237:.
224:.
202:.
187::
167:.
160::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.