Location of Dimensional Facilities in a Continuous Space - Location Science - page 144

Note that in contrast to minsum hyperplane location problems, the result also
holds for gauges. This was shown for D D 2 in Schöbel ( 1999a ) and for arbitrary
D recently in Plastria and Carrizosa ( 2012 ). Using transversal theory, it can
furthermore be extended to metrics (under some mild conditions of monotonicity),
see Schöbel ( 1999a ) for the case of D D 2.
A geometric point of view was taken in Nievergelt ( 2002 ) for the Euclidean
case. He interprets the minmax hyperplane location problem as follows: locate
two parallel hyperplanes such that the set of existing points lies completely
between these two hyperplanes and minimize the distance between these parallel
hyperplanes. He shows that in an optimal solution the two hyperplanes are rigidly
supported by the points in V , i.e., there does not exist any other pair of parallel
hyperplanes enclosing all points and passing through the same points of V .This
property coincides with the blockedness property of Theorem 7.7 . The algorithm
proposed in Nievergelt ( 2002 ) uses projective shifts to improve a solution in a finite
number of steps.

7.3.5 Algorithms for Minsum and Minmax Hyperplane

Location

We describe the main approaches used for computing minsum hyperplanes.

7.3.5.1 Enumeration

Theorems 7.2 , 7.4 ,and 7.7 specify a finite dominating set for both the minsum
and the minmax hyperplane location problem. The trivial approach is to enumerate
all candidates in the FDS. For the minsum case these are just the hyperplanes
passing through D of the existing points. More effort is necessary to determine
the hyperplanes being at maximum distance from D C 1 of the existing points for
the minmax case. For D D 2 and norm-based distances these are parallel to one
edge of the convex hull of the existing points (Schöbel 1999a ).

7.3.5.2 Linear Programming for Hyperplane Location with Vertical

and Block Norm Distances

For the vertical distance d ver the hyperplane location problem can be formulated as
a linear program. To this end, we define additional variables d j 0 which contain
the distances d.H;v j /;j D 1;:::;n. For the minsum problem we then obtain

X

n

minimize w j d j (7.9)

jD1