Information Technology Reference
In-Depth Information
S
in the sense that it places the
j
-th point at
P
θ
(
j
) := (cos
ʸ
j
,
sin
ʸ
j
), where
S
is the set of feasible strategies (specified later). The reason why a strategy is
denoted thus simply is that any adaptive decision based on the history of the
configuration does not help in this problem. When
k
points have arrived so far
and been placed according to the strategy
A
strategy
for placing points is denoted by a sequence
θ
:= (
ʸ
1
,ʸ
2
,...
)
∈
θ
, the center of mass of the points
lies at
G
θ
(
k
):=
1
k
sin
ʸ
j
.
k
k
cos
ʸ
j
,
1
k
j
=1
j
=1
Then, the cost of the strategy
θ
is written as
1
k
cos
ʸ
j
2
+
1
k
sin
ʸ
j
2
k
k
C
θ
(
k
):=
OG
θ
(
k
)=
.
j
=1
j
=1
On the other hand, the
optimal oine cost
, that is, one with the cardinality
known to be
k
in advance, is
C
opt
(
k
):=inf
{
C
θ
(
k
)
|
θ
∈
S
}
.
The performance of strategies for online problems is usually measured by the
competitive ratio (see [
2
] for example), which would be defined as sup
k≥
1
C
θ
(
k
)
C
opt
(
k
)
for our problem. However, this is inconvenient here since
C
opt
(
k
)=0and
C
θ
(
k
)
>
0 happen often in the same time. We thus define and use the
competi-
tive difference
instead. We say that the strategy
θ
has a competitive difference
of
d
if
C
θ
(
k
)
−
C
opt
(
k
)
≤
d
holds for all
k
≥
1. Apparently,
d
≥
0. A smaller competitive difference means a
better strategy.
In this paper we consider the online weight balancing problem under two
different settings:
(A) The
basic problem
. We are allowed to place a point on an arbitrary position
on the unit circle. Namely, the set of feasible strategies
S
is
{
(
ʸ
1
,ʸ
2
,...
)
|
0
≤
ʸ
j
<
2
ˀ
for
j
≥
1
}
.
(B) The
n
-cyclotomic problem
. For fixed
n
, the destination of each point is
chosen from
(cos
2
k
n
,
sin
2
k
n
, that is, a set of
n
positions that equally divide the unit circle into
n
arcs. Any position should
not be occupied more than once. Formally, we set
S
to
2
m
1
ˀ
n
{
|
≤
k
≤
n
−
1
,k
∈
Z
}
)
0
,
2
m
2
ˀ
n
,...,
2
m
n
ˀ
n
n
for 1
0
≤
m
j
≤
n
−
1
,m
j
∈
Z
≤
j
≤
n
;
n
.
m
j
=
m
k
for 1
≤
j<k
≤
We assume in addition that the cardinality of the arriving points is at most
n
.
Search WWH ::
Custom Search