Geoscience Reference
In-Depth Information
path of the tree is an absolute center and that the distance is a convex function along
any path of the tree. Given any node v
i
, the algorithm first determines the vertex v
j
whose distance to v
i
is maximum, then determines the node v
k
whose distance to
v
j
is maximum. The path linking v
j
and v
k
is a longest one and the absolute center
is its midpoint.
Kariv and Hakimi (
1979
) provided an O.
nlogn
/ algorithm for the weighted
center problem on a tree, which was improved to O.n/ by Megiddo (
1983
).
For an arbitrary graph G and p
2, Kariv and Hakimi (
1979
) proved that the
p-center problem is NP-hard even on a planar graph where the maximum degree is
3 and all node weights and edge lengths are equal to 1. The result is also true for
the vertex-restricted problem. The authors show that the problem with p
2 can be
solved in O.n
2
log
n/ time when G is a tree.
Hochbaum and Shmoys (
1985
) developed a two-approximation algorithm for the
unweighted discrete problem with I
D
J and edge lengths satisfying the triangle
inequality. The algorithm runs in O.
j
E
j
log
j
E
j
/ time. Hsu and Nemhauser (
1979
)
proved that it is NP-hard to find an approximation with a better guarantee. Dyer and
Frieze (
1985
)gaveanO.
np
/ algorithm with a guarantee of min
f
3;1
C
Ǜ
g
,whereǛ
is the ratio of the largest weight and the minimum weight. In the unweighted case,
this guarantee is 2.
4.3
Exact Methods for
p
-Center Problems
We first observe that the different variants of the p-center problem can be trans-
formed into a discrete p-center problem and solved as such.
In the case of the vertex-restricted p-center problem, the set I of possible
locations and the set J of demand points are both equal to the set of vertices V .
The weighted and unweighted absolute p-center problems enjoy the same
property as their single facility counterpart: an optimal solution can always be found
in the set of vertices and intersection points. This follows from the fact that each
point x
i
of an optimal solution X
p
must be a local minimizer of the function given
by the maximum (possibly weighted) distance to the vertices that are allocated to
x
i
, i.e., which are closer to that x
i
than to any other point of X
p
. To transform an
absolute p-center problem into a discrete p-center problem one thus simply sets
I
D
V
[
P,whereP denotes the set of intersection points, and J
D
V .
The remainder of this section is now devoted to models and algorithms for
solving the discrete p-center problem.
Several methods based on solving finite series of an auxiliary problem called the
set covering problem are developed. The set covering problem is a kind of covering
problem (see Chap.
5
), which is closely related to the p-center problem. Given a
zero-one matrix A
D
Œa
ji
, the set covering problem consists of finding a set of
columns at minimum cost that covers the rows of the matrix A. In order to minimize
the number of facilities required to serve all customers within a given radius value
