1-center problem

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

1-center problem, also called minimax location problem, asks: where should a single facility be placed so the farthest demand point is as close as possible? You have a set of demand points, a set of allowable facility locations, and a way to measure the cost (distance) from the facility to each demand point. The goal is to minimize the largest distance to any demand point.

There are many versions depending on where the points lie and how distance is measured. A common case is in the plane using straight-line (Euclidean) distance: the planar Euclidean 1-center problem, also known as the smallest enclosing circle, since the facility should be at the center of the smallest circle that contains all points. In higher dimensions you get the smallest enclosing ball.

A weighted version lets each demand point have a weight and minimizes the sum of distance times weight.

Some related problems include the closest string problem, where the inputs are strings and distance is the Hamming distance.

In graph terms, the 1-center can be seen as choosing a center in a weighted complete graph to minimize the maximum edge length to any demand point. A related idea is the minimax path problem, which minimizes the maximum weight along a path between two chosen vertices.