Facility Location - Minimax Facility Location

The minimax facility location problem seeks a location which minimizes the maximum distance to the sites, where the distance from one point to the sites is the distance from the point to its nearst site. A formal definition is as follows: Given a point set P ⊂ ℝd, find a point set S ⊂ ℝd, |S|=k, so that max_q∈S(minp∈P(d(p,q)) ) is minimized.

In the case of the Euclidean metric for k=1, it is known as the smallest enclosing sphere problem or 1-center problem. Its study traced at least to the year of 1860. see smallest enclosing circle and bounding sphere for more details.