Geoscience Reference
In-Depth Information
Similar to the situation in the previous section one can test whether the cell C
2
C
collapses with respect to f
1
;:::;f
Q
by comparing the gradients of the objective
functions in int.C/. Finally we obtain the following theorem, which can be proven
using the same reasoning as in the three-criteria case (see proof of Theorem
9.6
).
Theorem 9.8
0
@
1
A
X
Par
f
1
;:::;f
Q
D
S
S
encl
Par
.
f
p
;f
q
;f
r
/
gen
Par
.
f
p
;f
q
;f
r
/
[
gen
p<q<r
X
X
p;q;r2
Q
p;q;r2
Q
p<q<r
8
<
:
9
=
;
encl
X
Par
.f
p
;f
q
;f
r
/
;x2 col
Q
.C/
W9C 2
C
;C
S
p;q
p<q
X
wPar
.f
p
;f
q
/ n
S
gen
2
n
x 2
R
2
Q
p;q;r
2
Q
p<q<r
For the Q-criteria median problem we obtain the following algorithm.
Algorithm 9.3
Step 1.
Compute the subdivision of the plane generated
C
,the
X
wPar
.f
p
;f
q
/; p;q
2
family of elementary convex sets. Compute
Q
;p<q;
using Algorithm
9.1
.
Step 2.
Set for any
p
,
q
and
r
with
p<q<r
gen
Par
.f
p
;f
q
;f
r
/
WD
wPar
.f
p
;f
q
/
[
wPar
.f
p
;f
r
/
[
wPar
.f
q
;f
r
/;
X
X
X
X
and
Par
f
1
;:::;f
Q
WD
[
p;q;r
Par
.f
p
;f
q
;f
r
/
[
[
p;q;r
encl
X
Par
.f
p
;f
q
;f
r
/
:
gen
gen
X
X
2
Q
p<q<r
2
Q
p<q<r
For every cell
C
S
p;q
p<q
X
wPar
.f
p
;f
q
/
n
S
encl
X
gen
Par
.f
p
;f
q
;
Step 3.
2
Q
p;q;r
2
Q
p<q<r
X
Par
f
1
;:::;f
Q
WD
X
Par
f
1
;:::;f
Q
n
f
r
//
compute
col
Q
.C/
and set
col
Q
.C/
.
Output:
X
Par
f
1
;:::;f
Q
.
The complexity of Algorithm
9.3
can be determined as follows. For each
cell C,
col
Q
.C/ can be computed in O.Qlog.Q// time. Algorithm
9.3
needs
to solve O.Q
3
/ three-criteria problems which dominates all other elementary
operations of the algorithm. Each one of them has the same complexity as the
two-criteria problem. Thus, the overall complexity is O.M
3
G
max
Q
3
.log G
max
/
C
M
2
G
max
Q log Q/
D
O.M
3
G
max
Q
3
.log G
max
/.
We would like to conclude this section pointing that the multi-facility versions
of the problems analyzed in this section have been hardly studied in the literature,
although an exception is the paper by Nickel (
1997
).
