THREE ADD PROCEDURES FOR LOCATION IN THE PLANE
Søren Dahlerup, Søren Kruse Jacobsen and Henrik Juel
Abstract
We consider the p-median model in the plane with Euclidean distances.
The paper addresses the problem of ADDing one new facility to a set of
p-1 existing facilities in order to serve a given set of clients.
Three ADD procedures are proposed; the first one is based on search
for the subset of clients to be served by the new facility;
the two next algorithms are based on geometric considerations;
one with low storage demand and rather high computing time and,
one with high storage demand and rather low computing time.
The basic problem that arises when moving from the discrete case to the
Euclidean plane is that the number of feasible locations for a new facility
becomes infinite. It turns out however, that the maximum saving may
be found by repeated applications of the classical Weiszfeld algorithm.
Some computational experience is reported.
IMM Technical Report 13/95