The 1-center problem, also known as minimax problem or minmax location problem, is a classical
combinatorial optimization problem in
operations research
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve deci ...
of
facilities location
The study of facility location problems (FLP), also known as location analysis, is a branch of operations research and computational geometry concerned with the optimal placement of facilities to minimize transportation costs while considering fac ...
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
The smallest-circle problem (also known as minimum covering circle problem, bounding circle problem, least bounding circle problem, smallest enclosing circle problem) is a mathematical problem of computing the smallest circle that contains all of ...
. Its generalization to ''n''-dimensional
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
s is known as the
smallest enclosing ball
Small may refer to:
Science and technology
* SMALL, an ALGOL-like programming language
* Small (anatomy), the lumbar region of the back
* ''Small'' (journal), a nano-science publication
* <small>, an HTML element that defines smaller text
...
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 In theoretical computer science, the closest string is an NP-hard computational problem, which tries to find the geometrical center of a set of input strings.
To understand the word "center", it is necessary to define a distance between two string ...
problem, arises when the inputs are
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
and their distance is measured using
Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chan ...
.
The 1-center problem can be restated as finding a
star
A star is an astronomical object comprising a luminous spheroid of plasma (physics), plasma held together by its gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked ...
in a weighted
complete graph 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
* Desire p ...
between two selected vertices, in place of a star, is called the
minimax path 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
See also
*
Minsum facility location (
1-median problem), with
geometric median
In geometry, the 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 ...
being a special case
*
Maxmin facility location (
obnoxious facility location)
*
k-center problem
*
k-median problem
In statistics, ''k''-medians clusteringP. S. Bradley, O. L. Mangasarian, and W. N. Street, "Clustering via Concave Minimization," in Advances in Neural Information Processing Systems, vol. 9, M. C. Mozer, M. I. Jordan, and T. Petsche, Eds. Cambridg ...
Combinatorial optimization