1-center problem
Encyclopedia
The 1-center problem or minimax or minmax location problem is a classical combinatorial optimization
problem in operations research
of facilities location type. In its most general case the problem is stated as follows: given a set of n demand points, a space of feasible locations of a facility and a function to calculate the transportation cost between a facility and any demand point, find a location of the facility which minimizes the maximum facility-demand point transportation cost.
The simple special case when the feasible locations and demand points are in the plane with Euclidean distance as transportation cost (planar minmax Euclidean facility location problem, Euclidean 1-center problem in the plane, etc.), it is also known as the smallest circle problem
. Its generalization to n-dimensional Euclidean spaces is known as the smallest enclosing ball problem. A further generalization (weighted Euclidean facility location) is when the set of weights is assigned to demand points and the transportation cost is the sum of the products of distances by the corresponding weights.
There are numerous particular cases of the problem, depending on the choice of the locations both of demand points and facilities, as well as the distance function.
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
problem in operations research
Operations research
Operations research is an interdisciplinary mathematical science that focuses on the effective use of technology by organizations...
of facilities location type. In its most general case the problem is stated as follows: given a set of n demand points, a space of feasible locations of a facility and a function to calculate the transportation cost between a facility and any demand point, find a location of the facility which minimizes the maximum facility-demand point transportation cost.
The simple special case when the feasible locations and demand points are in the plane with Euclidean distance as transportation cost (planar minmax Euclidean facility location problem, Euclidean 1-center problem in the plane, etc.), it is also known as the smallest circle problem
Smallest circle problem
The smallest circle problem or minimum covering circle problem is a mathematical problem of computing the smallest circle that contains all of a given set of points in the Euclidean plane. The corresponding problem in n-dimensional space, the smallest bounding sphere problem, is to compute the...
. Its generalization to n-dimensional Euclidean spaces is known as the smallest enclosing ball problem. A further generalization (weighted Euclidean facility location) is when the set of weights is assigned to demand points and the transportation cost is the sum of the products of distances by the corresponding weights.
There are numerous particular cases of the problem, depending on the choice of the locations both of demand points and facilities, as well as the distance function.
See also
- Minsum facility location (1-median problem), with geometric medianGeometric medianThe geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points. This generalizes the median, which has the property of minimizing the sum of distances for one-dimensional data, and provides a central tendency in higher...
being a special case - Maxmin facility location (obnoxious facility location)
- k-center problem
- k-median problem