Information Technology Reference
In-Depth Information
achieves a competitive difference of zero for n =3 and n =5 , and a competitive
difference of
1
3cos 14
( < 0 . 35) for n
7 .
=(0 , 2 3 , 4 3 ). By rotational symmetry,
there is no choice of strategy. One can easily see that our strategy achieves a
competitive difference of zero.
For n =5,wehave
Proof. For n = 3, our strategy is
θ
=(0 , 2 5 , 4 5 , 6 5 , 8 5 ). Observe each time when the k -th
θ
item has arrived (1
5). One can confirm that there is no better placement
than that of our strategy, even if the cardinality is known in advance. Thus, our
strategy achieves a competitive difference of zero for n =5.
In the rest of the proof we discuss n
k
7. We calculate the coordinate of the
center of mass using the identities
cos
,
k
cos ( j
1)( n
1) ˀ
1
2cos 2 n
2 n +sin (2 k
ˀ
1)( n
1) ˀ )
=
n
2 n
j =1
sin
.
k
sin ( j
1)( n
1) ˀ
1
2cos 2 n
ˀ
2 n
sin (2 k ( n
1) + 1) ˀ
2 n
=
n
j =1
After some manipulation, we have
sin k ( n 1) ˀ
2 n
C θ ( k )=
.
2 n
k cos
C opt ( k ) for all k .For k =1,wehave
C θ (1) = 1 and obviously C opt (1) = 1. Therefore the difference is zero. For
k = 2, we immediately have C θ (2) = sin 2 n . By a simple calculation, it turns out
that to place two points at (1 , 0) and (cos ( n 1) ˀ
n
We investigate the value of C θ ( k )
, sin ( n 1) ˀ
n
) is optimal. Thus,
2 n . Hence, the difference is again zero. For k
C opt (2) = sin
3, by applying
C opt ( k )
0, we have
sin k ( n 1) ˀ
2 n
C θ ( k )
C opt ( k )
C θ ( k )=
.
2 n
k cos
We derive
sin k ( n− 1) ˀ
2 n
1
k cos 2 n
1
3cos 2 n
1
3cos 14
,
k cos 2 n
1 for all x ,cos 2 n
since sin x
decreases monotonically with n ,and n
7. The
1
3cos 14
competitive difference of the strategy
θ
is thus upper-bounded by
( < 0 . 35)
for n
7.
We leave some remarks without proof: For n = 7, the strategy (0 , 6 7 , 10 7 , 4 7 ,
12 7 , 2 7 , 8 7 ) has a competitive difference of zero, while the competitive ratio of
our strategy (0 , 6 7 , 12 7
, 4 7 , 10 7
, 2 7 , 8 7 ) is approximately 0 . 08. For n =9,the
Search WWH ::




Custom Search