107:
If G is a c-competitive randomized algorithm against any adaptive online adversary, and there is a randomized d-competitive algorithm against any oblivious adversary, then G is a randomized (c * d)-competitive algorithm against any adaptive offline
76:
is sometimes called the strong adversary. This adversary knows everything, even the random number generator. This adversary is so strong that randomization does not help against it.
43:. For deterministic algorithms, the adversary is the same as the adaptive offline adversary. For randomized online algorithms competitiveness can depend upon the
104:
If there is a randomized algorithm that is α-competitive against any adaptive offline adversary then there also exists an α-competitive deterministic algorithm.
62:
is sometimes referred to as the weak adversary. This adversary knows the algorithm's code, but does not get to know the randomized results of the algorithm.
118:
36:
69:
is sometimes called the medium adversary. This adversary must make its own decision before it is allowed to know the decision of the algorithm.
155:
218:
55:
The three common adversaries are the oblivious adversary, the adaptive online adversary, and the adaptive offline adversary.
223:
170:
151:
185:
128:
123:
32:
28:
17:
93:
212:
141:
97:
85:
166:
89:
145:
203:
189:
171:"On the Power of Randomization in On-line Algorithms"
8:
204:Bibliography of papers on online algorithms
147:Online Computation and Competitive Analysis
119:Competitive analysis (online algorithm)
7:
169:; G. Tardos; A. Wigderson. (1994).
25:
150:. Cambridge University Press.
1:
18:Adversary (online algorithm)
240:
165:S. Ben-David; A. Borodin;
74:adaptive offline adversary
67:adaptive online adversary
144:; El-Yaniv, R. (1998).
219:Analysis of algorithms
84:From S. Ben-David,
60:oblivious adversary
190:10.1007/BF01294260
51:Common adversaries
39:against different
224:Online algorithms
157:978-0-521-56392-5
80:Important results
16:(Redirected from
231:
193:
175:
161:
129:Online algorithm
124:K-server problem
41:adversary models
33:online algorithm
29:computer science
21:
239:
238:
234:
233:
232:
230:
229:
228:
209:
208:
200:
173:
164:
158:
140:
137:
115:
82:
53:
45:adversary model
37:competitiveness
23:
22:
15:
12:
11:
5:
237:
235:
227:
226:
221:
211:
210:
207:
206:
199:
198:External links
196:
195:
194:
162:
156:
136:
133:
132:
131:
126:
121:
114:
111:
110:
109:
105:
81:
78:
52:
49:
24:
14:
13:
10:
9:
6:
4:
3:
2:
236:
225:
222:
220:
217:
216:
214:
205:
202:
201:
197:
191:
187:
183:
179:
172:
168:
163:
159:
153:
149:
148:
143:
139:
138:
134:
130:
127:
125:
122:
120:
117:
116:
112:
106:
103:
102:
101:
99:
95:
91:
87:
79:
77:
75:
70:
68:
63:
61:
56:
50:
48:
46:
42:
38:
35:measures its
34:
30:
19:
181:
178:Algorithmica
177:
146:
98:A. Wigderson
83:
73:
71:
66:
64:
59:
57:
54:
44:
40:
26:
142:Borodin, A.
213:Categories
135:References
108:adversary.
86:A. Borodin
100:we have:
94:G. Tardos
184:: 2–14.
113:See also
167:R. Karp
90:R. Karp
154:
47:used.
174:(PDF)
31:, an
152:ISBN
72:The
65:The
58:The
186:doi
27:In
215::
182:11
180:.
176:.
96:,
92:,
88:,
192:.
188::
160:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.