On the continuous Weber and kmedian problems
Fekete, Sandor P. and Mitchell, Joseph S. B. and Weinbrecht, Karin
(2000)
On the continuous Weber and kmedian problems.
Published In:
Proceedings of the Sixteenth Annual Symposium on Computational Geometry : SCG '00 ; June 12  14, 2000, Hong Kong ACM 2000, pp. 7079.
Abstract
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 kmeans (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 polynomialtime algorithms for various versions of the L1 1mean (Weber) problem. We also consider the multiplecenter version of the L1 kmeans problem, which we prove is NPhard for large k.
Download: 
Postscript
 Preprinted Version
Download (481kB)  Preview 

Editorial actions:  View Item (Login required) 
Item Type:  Proceedings article 

Citations:  27 (Google Scholar)  
Uncontrolled Keywords:  computational complexity computational geometry continuous demand geometric optimization kmeans location theory median rectilinear norm shortest paths Weber problem 
Subjects: 

Divisions:  Mathematical Institute 
Related URLs: 
ZAIK Number:  zaik1999378 

Depositing User:  Archive Admin 
Date Deposited:  02 Apr 2001 00:00 
Last Modified:  16 Jan 2012 13:32 
URI:  http://earchive.informatik.unikoeln.de/id/eprint/378 