Geoscience Reference
In-Depth Information
but sets. We propose the use of a method discussed by Francis and Lowe
(
1992
). For motivation, consider the case where for each element
s
k
of
S
there
is only one “nearby” element of
Y
,say
y
k
ˆ
. In this case we might use either
max
f
d.s
k
;y
kO
/
W
k
D
1;:::;p
g
or
P
f
d.s
k
;y
kO
/
W
k
D
1;:::;p
g
as
diff
(
S
,
Y
).
More generally, define the
p
x
p
matrix
C
D
(
c
ij
) with
c
ij
D
d
(
s
i
,
y
j
). Define an
assignment (permutation matrix) to be any 0/1
p
p
matrix
Z
D
(
z
ij
) having a single
nonzero entry of one in each row, and a single nonzero entry of one in each column,
and let
P
denote the set of all such
p!
assignments (permutation matrices). Define
the objective function value
v
(
Z
) for every assignment
Z
2
P
by
v
(
Z
)
max
f
c
ij
z
ij
:
Z
2
P
g
,sothat
v
(
Z
) is the largest entry in C for which the corresponding entry in
Z
is one. Define (
S
,
Y
)
D
min
f
v
(
Z
):
Z
2
P
g
,sothat(
S
,
Y
) is the minimal objective
function value of the min-max assignment problem with cost matrix
C
. We propose
using (
S
,
Y
)for
diff
(
S
,
Y
). There are several good reasons for using (
S
,
Y
). One
reason is that it has all the properties of a distance (see Goldberg
1976
):
symmetry
:
(
S
,
Y
)
D
(
Y
,
S
);
nonnegativity
: (
S
,
Y
)
0and.S;Y/
D
0
()
S
D
Y ;
triangle inequality
: .S;Y/
.S;Z/
C
.Z;Y/for any
p
-servers
S
,
Y
and
Z
. Another reason, further explored in Francis et al. (
2009
), is that it is related to the
absolute error. (We could also use the optimal value of the conventional min-sum
assignment model for
diff
(
S
,
Y
). This optimal value also has all the properties of a
distance, but we know of no useful relationship between it and absolute error.) We
call the distance the
min-max distance
.Note,foranytwo
p
-servers
S
,
Y
ǝ,
(
S
,
Y
)
diam
(ǝ). Further, when
p
D
1 the min-max distance is just the usual
distance,
d
(
x
1
,
y
1
).
Both min-max and min-sum assignment models are well-studied and are effi-
ciently solvable in low polynomial order for any set of real coefficients (Ahuja et al.
1993
) . In the assignment models we study, the coefficients typically correspond
to distances between points in some geometric spaces, e.g., planar Euclidean or
rectilinear cases. For these geometric models significantly more efficient algorithms
have become available (Agarwal et al.
1999
; Agarwal and Varadarajan
1999
; Efrat
et al.
2001
; Varadarajan
1998
).
There are a number of relationships between the error measures of Table
18.2
.
These relationships, some of which may not be obvious, are a subject of discussion
in Francis et al. (
2009
), where there are also numerical examples of many of the
error measures. It also seems worth pointing out that error measures 2 through 7 of
Tab le
18.2
are local error measures, since they depend on
S
. By contrast, measures
1, 8 and 9 may be considered global error measures.
There is no general agreement on which aggregation error measure is best.
Until the research community agrees on one or more error measures, progress in
comparing various aggregation approaches, and in building a cumulative body of
knowledge, will necessarily be limited. The lack of agreement on error measures
also limits progress in trading off aggregation advantages and disadvantages.
Further, because comparisons of various aggregation algorithm results should all be
based on the same error measures, there is currently little point in developing a data
base of DPs that can be used by the profession to test their aggregation methods.
We personally recommend the uses of relative error based on absolute error
