On the Continuous Fermat-Weber Problem

Sándor P. Fekete (), Joseph S. B. Mitchell () and Karin Beurer ()
Additional contact information
Sándor P. Fekete: Institute for Mathematical Optimization, Braunschweig University of Technology, 38106 Braunschweig, Germany
Joseph S. B. Mitchell: Department of Applied Mathematics and Statistics, State University of New York, Stony Brook, New York 11794-3600
Karin Beurer: SAP AG, 69190 Walldorf, Germany

Operations Research, 2005, vol. 53, issue 1, 61-76

Abstract: 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 1-median (Fermat-Weber) problem. We also consider the multiple-center version of the L 1 k -median problem, which we prove is NP-hard for large k .

Keywords: facilities/equipment planning; continuous location:Fermat-Weber problem; continuous demand (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (11)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0137 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:53:y:2005:i:1:p:61-76

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().