1-center problem

The 1-center problem, also known as minimax problem or minmax location problem, is a classical <a href="/facts/Combinatorial_optimization/PTcloS79">combinatorial optimization</a> problem in <a href="/facts/Operations_research/H5yJkV5n">operations research</a> of <a href="/facts/Optimal_facility_location/ssbU6ww2">facilities location</a> 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 <a href="/facts/Smallest_circle_problem/S7W9mjad">smallest circle problem</a>. Its generalization to n-dimensional <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean spaces</a> is known as the <a href="/facts/Smallest_enclosing_ball/0lVclU4z">smallest enclosing ball</a> 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 <a href="/facts/Closest_string/8kaLYNzL">closest string</a> problem, arises when the inputs are <a href="/facts/String_(computer_science)/4ChJu5WS">strings</a> and their distance is measured using <a href="/facts/Hamming_distance/MgdtbYPo">Hamming distance</a>.
The 1-center problem can be restated as finding a <a href="/facts/Star_(graph_theory)/PNW0H6eK">star</a> in a weighted <a href="/facts/Complete_graph/AYD6hUqI">complete graph</a> that minimizes the maximum weight of the selected edges.
The corresponding problem of minimizing the maximum weight of a <a href="/facts/Path_(graph_theory)/WMsq21Nf">path</a> between two selected vertices, in place of a star, is called the <a href="/facts/Minimax_path_problem/f18dIR7F">minimax path problem</a>.

1-center problem open-in-new

1-center problem