Title
On the continuous Weber and k-median problems
Authors
-
Publication
Extended abstract in: 16th Annual Symposium on
Computational Geometry (SoCG 2000), 70-79
Source
-
Classification
-
| MSC: |
| primary: | 90B85 | Continuous location |
| secondary: | 68U05 | Computer graphics; computational geometry |
Keywords
-
location theory, Weber problem, k-median, median,
continuous demand, computational geometry,
geometric optimization, shortest paths,
rectilinear norm, computational complexity
-
-
We give the first exact algorithmic study of
facility location problems having a continuum of demand points.
In particular, we consider versions of the "continuous k-median
(Weber) problem" where the goal is to select one or more center
points that minimize average distance to a set of points in a
demand region. In such problems, the average is computed as an
integral over the relevant region, versus the usual discrete sum
of distances. The resulting facility location problems are
inherently geometric, requiring analysis techniques of computational
geometry. We provide polynomial-time algorithms for various versions
of the L1 1-median (Weber) problem. We also consider the
multiple-center version of the L1 k-median problem, which
we prove is NP-hard for large k.
