On the continuous Fermat-Weber problem
成果类型：
Article
署名作者：
Fekete, SP; Mitchell, JSB; Beurer, K
署名单位：
Braunschweig University of Technology; State University of New York (SUNY) System; Stony Brook University; SAP
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.1040.0137
发表日期：
2005
页码：
61-76
关键词：
摘要：
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 l-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.