Geoscience Reference
In-Depth Information
Infante-Macias and Muñoz-Perez (
1995
) discuss medianoid locations in the plane
with customer demand occurring at discrete points, and Manhattan distances are
used. A given parameter specifies how much closer a new facility must be to a
customer to be considered comparable, i.e., equally desirable. For the location of a
single new facility, the paper describes an
O
(
n
3
) algorithm, for a given number
p
of
new facilities, an
O
(
n
5
) algorithm is suggested.
14.4.5
UD1a, Networks, Nash Equilibria
Bhadury and Eiselt (
1995
) investigate duopoly models with fixed and equal prices
on tree networks. They describe locational Nash equilibria in case co-location (i.e.,
the location of both facilities at the same node) is permitted or not, and they describe
a measure of stability of the equilibrium, rather than applying the usual equilibrium-
no equilibrium dichotomy. In another paper, the same authors (Eiselt and Bhadury
1998
) discuss the reachability of Nash equilibria (assuming that at least one such
equilibrium exists) on trees. Starting with arbitrary locations of the duopolists, they
apply sequential and repeated short-term optimization to investigate whether or not
an equilibrium will be reached. The answer is it will, provided an appropriate tie-
breaking rule is employed. Eiselt and Laporte (
1993
) describe conditions, under
which a three-facility problem on a tree has agglomerated, dispersed, and no
equilibria.
14.4.6
UD1a, Networks, von Stackelberg Solution
Among the early contributions, Slater's (
1975
) work stands out. In it, the author
introduces leader and follower, respectively, does, however, not make the connection
to von Stackelberg's work. The paper proves that on a tree network, the location
leader will locate at the median. In his contribution, Hakimi (
1983
) first introduces
von Stackelberg games by referring to the locations of the leader(s) of the sequential
game as
centroids
(based on their maximin objective), while the locations of the
follower(s) are termed
medianoids
(as their objective is of the “minisum” type).
In particular, if the leader has already located p facilities in a pattern denoted by
X
p
, and if the follower is poised to locate
r
facilities, the follower's problems is
an (
r
j
X
p
) medianoid. On the other hand, if a leader wants to locate
p
facilities,
knowing/assuming that the follower will locate
r
facilities, we talk about an (
r
j
p
)
centroid. Hakimi discusses a number of results of special cases regarding the node
property, i.e., the question whether or not at least one optimal location pattern
naturally has locations at the nodes of the given network. In addition, he proves the
NP
-hardness of (
r
j
X
1
) medianoid of general networks as well as the
NP
-hardness
of the (1
j
p
) centroid. In the same year, Megiddo et al. (
1983
) show a polynomial
O(
n
2
r
) algorithm for the (
r
j
X
p
) medianoid problem on trees. Penn and Kariv (
1989
)
