On the continuous Fermat–Weber problem

On the continuous Fermat–Weber problem

0.00 Avg rating0 Votes
Article ID: iaor20073543
Country: United States
Volume: 53
Issue: 1
Start Page Number: 61
End Page Number: 76
Publication Date: Jan 2005
Journal: Operations Research
Authors: , ,
Keywords: facilities
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 L1 1-median (Fermat–Weber) problem. We also consider the multiple-center version of the L1 k-median problem, which we prove is NP-hard for large k.

Reviews

Required fields are marked *. Your email address will not be published.