Information Technology Reference
In-Depth Information
strategy (0
,
8
9
,
14
9
,
4
9
,
12
9
,
2
9
,
6
9
,
16
9
,
10
9
) has a better competitive difference
than that of our strategy (0
,
8
9
,
16
9
,
6
9
,
14
9
,
4
9
,
12
9
,
2
9
,
10
9
). That is to say,
our strategy is not optimal for these cases.
In addition, our strategy is not optimal for large
n
; roughly speaking, a strat-
egy more like that presented in Theorem
1
performs better. More specifically, one
can have a better strategy by rounding each position specified in the strategy in
Theorem
1
into some nearby position that is feasible for the
n
-cyclotomic prob-
lem, in such a way that each position does not occur more than once. Although
the rounded positions for later points may be far from those in the original strat-
egy, this does not matter. Recall that the positions for later points do not affect
the competitiveness, as we discussed in Sect.
3.1
.
Theorem 3.
For the
n
-cyclotomic problem with even
n
(
≥
2)
, the strategy
θ
defined as
ʸ
j
=
(
j
−
1)
ˀ
,
j
is odd
;
n
(
j−
2)
ˀ
n
+
ˀ,
j
is even
achieves a competitive difference of zero for
n
=4
, and a competitive difference
of
1
3
for
n
≥
6
.
Proof.
For
n
= 4, the strategy obviously has a competitive difference of zero;
there is no choice of strategy.
For
n
≥
6 we first derive
C
θ
(
k
) in a closed form. It is observed that every two
angles in
place two points so that they form a diameter. Therefore, for even
k
, the center of mass lies at the origin and
C
θ
(
k
) = 0. Apparently,
C
θ
(1) = 1.
What remains is odd
k
θ
1) = 0 for such
k
.
The center of mass after placing the
k
-th point can be considered as the center
of mass of the following two weighted points: a point with weight of
k
≥
3. We have already known
C
θ
(
k
−
1atthe
origin and one with unit weight at
P
θ
(
k
) on the unit circle. Hence, the center
of mass
of the
k
points divides the line segment
OP
θ
(
k
) in the ratio 1 :
k
−
−
1.
1
1+(
k−
1
k
Noting
OP
θ
(
k
)=1,wehave
C
θ
(
k
)=
1)
=
for odd
k
.
C
opt
(
k
) for all
k
.For
k
=1,wehave
C
opt
(1) = 1 and thus the difference is zero. For odd
k
We next check the value of
C
θ
(
k
)
−
≥
3, we obtain
C
θ
(
k
)=
1
1
3
,
C
θ
(
k
)
−
C
opt
(
k
)
≤
k
≤
since
C
opt
(
k
)
≥
0 holds. For even
k
≥
2, we have
C
θ
(
k
)
−
C
opt
(
k
)
≤
C
θ
(
k
)=0
.
We thus conclude that the competitive difference of the strategy
θ
is at
1
3
.
most
We add without proof that not only for
n
= 4 but also for
n
=6,8,and10,
o
u
r strategy is an optimal stra
t
egy. The competitive difference is
1
3
for
n
=6,
√
2
0
.
20) for
n
=8,and
√
5
−
1
6
−
1
0
.
21) for
n
= 10. For large
n
, however, it
turns out that our strategy is not optimal by the same reason as for large odd
n
.
(
≈
(
≈
3
Search WWH ::
Custom Search