Geoscience Reference
In-Depth Information
This chapter is organized as follows. We review some polynomial cases, identify
the complexity of the problems in general and present some approximation results
in Sect.
4.2
. Section
4.3
is devoted to the mixed integer linear programming models
and algorithms for solving p-center problems. Heuristics are discussed in Sect.
4.4
and some extensions of the p-center problem are considered in Sect.
4.5
. Section
4.6
concludes the chapter.
4.2
Polynomial Cases, Complexity and Approximation
Results
An algorithm to compute an absolute center of a graph was proposed by Hakimi
(
1964
). The idea is to compute, for each edge, an optimal point assuming that
the center is restricted to be on that edge. Such an optimal point is called a local
center of that edge. Then the algorithm finds the best local center. Hence, the
overall complexity is equal to the number of edges multiplied by the complexity
of computing a local center of an edge.
The computation of a local absolute center is based on the observation that the
objective function is piecewise linear on each edge and that local minima correspond
to
intersection points
and vertices (see Minieka
1970
). A point x on edge
f
v
k
;v
m
g2
E qualifies as an intersection point if there exist two distinct nodes v
i
;v
j
2
V such
that x is the unique point on
f
v
k
;v
m
g
for which d.v
i
;x/
D
d.v
i
;v
k
/
C
d.v
k
;x/
D
d.x;v
j
/
D
d.x;v
m
/
C
d.v
m
;v
j
/.
It follows from this definition that the number of intersection points on an edge
is bounded by O.n
2
/. Nevertheless, Kariv and Hakimi (
1979
) observed that at most
n
C
1 such points can be local minima of the objective function. The resulting
algorithm proposed by Kariv and Hakimi (
1979
) solves the absolute center problem
in O.
j
E
j
n
C
n
2
log
n/ time.
An algorithm for finding an absolute center in the weighted case can be derived
along the same lines. First, a solution can also be found in the set of local centers,
i.e., solutions to the problems in which the solution is restricted to be on an edge.
Then, the objective function remains piecewise linear on each edge but the slopes
of the linear pieces depend on the vertex weights
w
j
. Kariv and Hakimi (
1979
)
showed that, on an edge, at most 3n
2 intersections points can determine a local
minima. A point x on an edge
f
v
k
;v
m
g
is now an intersection point if there exist
two distinct nodes v
i
;v
j
2
V such that x is the unique point on
f
v
k
;v
m
g
for which
w
i
d.v
i
;x/
D
w
i
.d.v
i
;v
k
/
C
d.v
k
;x//
D
w
j
d.x;v
j
/
D
w
j
.d.x;v
m
/
C
d.v
m
;v
j
//.
The complexity of the resulting algorithm proposed by Kariv and Hakimi (
1979
)is
O.
j
E
j
nlog
n/.
Goldman (
1972
) proposed an O.n
2
/ algorithm to find an absolute center of a tree
in the unweighted case. The algorithm checks whether an edge contains an absolute
center and if not, searches the two subtrees obtained by deleting this edge. Handler
(
1973
) proposed an O.n/algorithm exploiting the fact that the midpoint of a longest
