This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Fekete, S. P. Articles by Beurer, K. Search for Related Content

On the Continuous Fermat-Weber Problem

Institute for Mathematical Optimization, Braunschweig University of Technology, 38106 Braunschweig, Germany
Department of Applied Mathematics and Statistics, State University of New York, Stony Brook, New York 11794-3600
SAP AG, 69190 Walldorf, Germany
sandor.fekete{at}tu-bs.de
jsbm{at}ams.sunysb.edu
karin.beurer{at}sap.com

We give the first exact algorithmic study of facility location problems that deal with finding a median for a continuum of demand points. In particular, we consider versions of the "continuous k-median (Fermat-Weber) problem" where the goal is to select one or more center points that minimize the 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 L₁ 1-median (Fermat-Weber) problem. We also consider the multiple-center version of the L₁ k-median problem, which we prove is NP-hard for large k.

Subject classifications: facilities/equipment planning; continuous location:Fermat-Weber problem; continuous demand.
History: Received April 2001; revision received July 2003; accepted November 2003.