On the continuous Fermat-Weber problem

Details On the continuous Fermat-Weber problem On the continuous Fermat-Weber problem

2003-10-15

arxiv.org/abs/cs/0310027v1

Computer Science

Computational Geometry

28 pages, 18 figures, Latex, to appear in Operations Research, extended abstract version appeared in SoCG 2000

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On the continuous Fermat-Weber problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the continuous Fermat-Weber problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the continuous Fermat-Weber problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-527501