Hardware Reference
In-Depth Information
In order not to lose with respect to the previous case, the adversary has to choose the
value of
C
2
so that
ϕ
1
≤
ϕ
0
; that is,
1
k
+
C
2
≤
k
−
1
k
,
which means
k
2
C
2
≥
−
2
k.
However, observe that, if
ϕ
1
<ϕ
0
, the execution of
J
0
would be more convenient for
the player; thus the adversary decides to make
ϕ
1
=
ϕ
0
; that is,
=
k
2
C
2
−
2
k.
Case i
. If the player decides to schedule
J
i
, the sequence terminates with
J
i
+1
. In this
case, the cumulative value gained by the player is
C
i
, whereas the one obtained by
the adversary is (
C
0
+
C
1
+
...
+
C
i
+1
). Hence, the ratio among the two cumulative
values is
C
i
j
=0
C
j
+
C
i
+1
ϕ
i
=
.
As in the previous case, to prevent any advantage to the player, the adversary will
choose tasks' values so that
1
k
.
ϕ
i
=
ϕ
i−
1
=
...
=
ϕ
0
=
Thus,
C
i
j
=0
C
j
+
C
i
+1
1
k
,
ϕ
i
=
=
and hence
i
C
i
+1
=
kC
i
−
C
j
.
j
=0
Thus, the worst-case sequence for the player occurs when major tasks are generated
with the following computation times:
C
0
=1
kC
i
−
j
=0
C
j
.
C
i
+1
=
Search WWH ::
Custom Search