Geoscience Reference
In-Depth Information
The center problem, defined as finding a vertex whose distance to all the other
vertices of a graph is minimum, has been known for a long time in graph theory
(see, for instance, Berge
1967
).
Hakimi (
1964
) introduced the absolute center problem to locate a police station
or a hospital such that the maximum distance of the station to a set of communities
connected by a highway system is minimized. Given a graph G
D
.V;E/ with
V
Df
v
1
;:::;v
n
g
, weight
w
j
for node v
j
2
V and length `
ij
for edge
f
i;j
g2
E
connecting nodes v
i
and v
j
, the aim of the
absolute center problem
is to find a
point x on the nodes or edges such that max
jD1;:::;n
w
j
d.v
j
;x/is minimized, where
d.v
j
;x/is the length of the shortest path between node v
j
and point x (referred to
as distance between v
j
and x). The optimal value is called the
absolute radius
of
graph G.Ifx is limited to the nodes of G, then we obtain the
center
of graph G and
the optimal value is the
radius
of G. The center of G is not necessarily an absolute
center of G. In other words, the absolute radius can be smaller than the radius. To
see this, consider a very simple example with two nodes of weight 1 and an edge
connecting them with length 1. In this example, the absolute radius is 0.5 whereas
the radius is 1.
Hakimi (
1964
) proposed a solution method to compute the absolute center of a
graph and motivated further studies of this problem by casting it as a game. Two
people, X and Y, are playing a game on a graph G. First player X chooses a point
x in G, then player Y chooses a point y in G and X pays d.x;y/ units to Y. When
X chooses point x, Y chooses a point farthest from x to maximize his gain. Hence,
player X computes the absolute radius of graph G to minimize his loss.
In the conclusion of his subsequent paper on median and covering problems,
Hakimi (
1965
) mentions the generalization of the absolute center problem to the
p-center problem. Given a set X
p
Df
x
1
;:::;x
p
g
of p points in G, the distance
d.X
p
;v
j
/ between X
p
and node v
j
is computed as min
iD1;:::;p
d.x
i
;v
j
/.The
p
-center problem
is to find a set X
p
of p points in G such that max
jD1;:::;n
w
j
d
.v
j
;X
p
/ is minimized.
As defined above, the p-center problem is a network location problem. The
literature contains several variants. In this chapter, we refer to the following
variants:
vertex-restricted
p
-center problem
: X
p
is restricted to be a subset of the node set;
unweighted
p
-center problem
: all node weights are equal;
discrete
p
-center problem
: the graph G
D
.J
[
I;E/ is bipartite and complete
with I denoting the set of possible facility locations and J denoting the set of
demand points.
One can find a discussion of several theoretical results and exact methods for
the p-center problem on general and tree networks in Tansel (
2011
). A large scale
review of the exact and heuristic methods proposed for the p-center and capacitated
p-center problems is provided by Calik (
2013
).
