Geoscience Reference
In-Depth Information
we refer to the
p
-center,
p
-median, and covering location model as PCM, PMM,
and CLM respectively. These models are NP-hard to minimize (Kariv and Hakimi
1979
; Megiddo and Supowit
1984
).
Consider several aggregation examples which serve to illustrate our notation and
basic aggregation ideas. Let
J
Df
1, :::,
n
g
denote the set of all DP indices. We
suppose, for these examples, that the DPs will be aggregated into two postal code
area centroids. Let
J
i
denote the subset of indices of the DPs in postal area
i
D
1, 2.
Let
i
denote the centroid of postal area
i
D
1, 2. Clearly, the
J
i
form a partition of
J
. To aggregate the DPs in the postal code areas into the centroids we replace each
v
j
with
j
2
J
i
,by
i
for i
D
1, 2. Thus v
0
j
D
i
for
j
2
J
i
and i
D
1, 2. Hence
V
0
is now
the
n
-vector of ADPs, and
Df
1
,
2
g
is the ADP set.
Example
PMM
: f.S
W
V/
D
P˚
w
j
D
S;v
j
W
j
2
J
.
aggregation
1,
Let !
1
D
P˚
w
j
W
j
2
J
1
;
2
D
P˚
w
j
W
j
2
J
2
.Wethenhavef.S
W
V
0
/
D
P
n
w
j
D
S;v
0
j
W
j
2
J
o
D
P˚
w
j
D.S;
1
/
W
j
2
J
1
C
P˚
w
j
D.S;
2
/
W
j
2
J
2
D
!
1
D.S;
1
/
C
!
2
D.S;
2
/. This example illustrates how aggregation error can
occur. If only
p
-servers are of interest (with
p
2), then taking
S
to be
f
1
,
2
g
minimizes
f
(
S
:
V
0
) with minimal value of 0, giving a useless underestimation of
min
f
f
(
S
:
V
):
S
g
.
If there is only one server,
S
Df
s
g
,andthe`
p
-distance is used, then it is known
that this 1-median under-approximation is valid for all
s
. Letting !
D
P
f
w
j
:
j
2
J
g
,
and
D
P
f
(
w
j
/!)
v
j
:
j
2
J
g
be the centroid of the DPs, so that
f
(
s
:
V
0
)
D
!
jj
s
jj
p
,
it is known (Francis and White
1974
)that
f
(
s
:
V
)
f
(
s
:
V
0
)forall
s
.Thisisan
important reason why underestimation can occur for PMM aggregation when few
centroid ADPs are used. It is also known that for `
p
distances (Plastria
2001
)the
difference
f
(
s
:
V
)
f
(
s
:
V
0
) goes to zero as
s
gets farther from along an infinite ray
with one end point at . There are good theoretical reasons due to self-canceling
error (Plastria
2000
,
2001
); (Francis et al.
2003
) for using centroids as ADPs for the
PMM, but none that we know of for the PCM and CLM. Indeed, better choices than
centroids are available for the latter two models.
Example aggregation 2, PCM
:
f
(
S
:
V
)
D
max
f
w
j
D
(
S
,
v
j
):
j
2
J
g
.Let
w
1
D
max
˚
w
j
W
j
2
J
1
;
w
2
D
max
˚
w
j
W
j
2
J
2
.Wethenhavef
S
W
V
0
D
max
˚
w
j
D
S;v
0
j
W
j
2
J
D
max
n
max
˚
w
j
D
S;v
0
j
W
j
2
J
1
,max
˚
w
j
D
S;v
0
j
W
j
2
J
2
D
max
˚
max
˚
w
j
D
S;
1
W
j
2
J
1
,max
˚
w
j
D
S;
2
W
j
2
J
2
o
D
max
˚
w
1
D
S;
1
;
w
2
D
S;
2
. Again, if only
p
-servers (
p
2) are of interest, then
taking
S
to be
f
1
,
2
g
minimizes
f
(
S
:
V
0
) with minimal value of 0, giving an
underestimate of
f
(
S
:
V
).
Example aggregation 3, CLM:
minimize
j
S
j
subject to
D
(
S
,
v
j
)
r
j
,
j
2
J
,
S
ǝ,where
r
j
is a “covering radius” associated with
v
j
. All but two covering
constraints for the aggregated model are redundant. Define
1
D
min
f
r
j
:
j
2
J
1
g
,
2
D
min
f
r
j
:
j
2
J
2
g
. Thus the aggregated model has constraints D.S;
1
/
1
;D.S;
2
/
2
;S
ǝ. This means it takes at most two servers to solve the
aggregated model. CLMs and PCMs are known to be closely related (Kolen and
