4
$\begingroup$

The Weber problem is a special case of a facilities location problem : In a basic formulation, the facility location problem consists of a set of potential facility sites L where a facility can be opened, and a set of demand points D that must be serviced. The goal is to pick a subset F of facilities to open, to minimize the sum of distances from each demand point to its nearest facility, plus the sum of opening costs of the facilities (from Wikipedia https://en.wikipedia.org/wiki/Facility_location_problem)

The Weber is the case where there is one facility and n demands (or clients)

The facilities location problem is NP-Hard if there is several facilities but is it still the case in the simpler form of the Weber problem ?

Improve this question
$\endgroup$
3
  • $\begingroup$ Assuming the additional cost is proportional to sum of distances, isn't this just a matter of finding a geometric (or graph-theoretic) centroid? Gerhard "Trying To Get To Center" Paseman, 2019.12.02. $\endgroup$
    – Gerhard Paseman
    Commented Dec 2, 2019 at 18:28
  • 1
    $\begingroup$ This may help: "Weiszfeld's Method: Old and New Results." Abs: "In 1937, the 16-years-old Hungarian mathematician Endre Weiszfeld, in a seminal paper, devised a method for solving the Fermat-Weber location problem--a problem whose origins can be traced back to the seventeenth century. Weiszfeld's method stirred up an enormous amount of research in the optimization and location communities, and is also being discussed and used till these days. In this paper, we review both the past and the ongoing research on Weiszfed's method." $\endgroup$
    – Joseph O'Rourke
    Commented Dec 2, 2019 at 18:48
  • 1
    $\begingroup$ I found this citation for the paper @Joseph refers to: Amir Beck & Shoham Sabach, 2015. "Weiszfeld’s Method: Old and New Results," Journal of Optimization Theory and Applications, Springer, vol. 164(1), pages 1-40, January. $\endgroup$
    – Gerry Myerson
    Commented Dec 2, 2019 at 21:57

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .