Optimal facility location under various distance functions Academic Article uri icon


  • We present efficient algorithms for two problems of facility location. In both problems we want to determine the location of a single facility with respect to n given sites. In the first we seek a location that maximizes a weighted distance function between the facility and the sites, and in the second we find a location that minimizes the sum (or sum of the squares) of the distances of k of the sites from the facility. 1. Introduction Facility location is a classical problem of operations research that has also been examined in the computational geometry community. The task is to position a point in the plane (the facility) such that a distance between the facility and given points (sites) is minimized or maximized. Most of the problems described in the facility location literature are concerned with finding a "desirable" facility location: the goal is to minimize a distance function between the facility (e.g., a service) and the sites (e.g., the customers). Just as important i...

publication date

  • January 1, 2000