On the continuous Weber and k-median problems

Fekete, Sandor P. and Mitchell, Joseph S. B. and Weinbrecht, Karin (2000) On the continuous Weber and k-median problems.
Published In: Proceedings of the Sixteenth Annual Symposium on Computational Geometry : SCG '00 ; June 12 - 14, 2000, Hong Kong ACM 2000, pp. 70-79.


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-means (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-mean (Weber) problem. We also consider the multiple-center version of the L1 k-means problem, which we prove is NP-hard for large k.

Download: [img] Postscript - Preprinted Version
Download (481kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zaik1999-378
Depositing User: Archive Admin
Date Deposited: 02 Apr 2001 00:00
Last Modified: 16 Jan 2012 13:32
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/378