The 1-center problem, also known as minimax problem or minmax location problem, is a classical
combinatorial optimization
Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combina ...
problem in
operations research
Operations research () (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a branch of applied mathematics that deals with the development and application of analytical methods to improve management and ...
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.
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.
A simple special case is 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 space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
s 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. Another special case, the
closest string problem, arises when the inputs are
strings and their distance is measured using
Hamming distance
In information theory, the Hamming distance between two String (computer science), strings or vectors of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number ...
.
The 1-center problem can be restated as finding a
star
A star is a luminous spheroid of plasma (physics), plasma held together by Self-gravitation, self-gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked eye at night sk ...
in a weighted
complete graph
In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
that minimizes the maximum weight of the selected edges.
The corresponding problem of minimizing the maximum weight of a
path
A path is a route for physical travel – see Trail.
Path or PATH may also refer to:
Physical paths of different types
* Bicycle path
* Bridle path, used by people on horseback
* Course (navigation), the intended path of a vehicle
* Desir ...
between two selected vertices, in place of a star, is called the
minimax path problem.
See also
*
Minimum-diameter spanning tree
In metric geometry and computational geometry, a minimum-diameter spanning tree of a finite set of points in a metric space is a spanning tree in which the diameter (the longest path length in the tree between two of its points) is as small as ...
*
Minsum facility location (
1-median problem), with
geometric median
In geometry, the geometric median of a discrete point set 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 or absolute ...
being a special case
*
Maxmin facility location (
obnoxious facility location)
*
k-center problem
*
k-median problem
References
*
*
*
*
* {{cite journal , last = Burkard , first = Rainer E. , author2= Helidon Dollani , title = A Note on the Robust 1-Center Problem on Trees , journal = Annals of Operations Research , volume = 110 , issue = 1–4 , pages = 69–82 , publisher = Kluwer Academic Publishers , date = February 2002 , issn = 1572-9338 , doi = 10.1023/A:1020711416254
Combinatorial optimization