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