1-center problem

Combinatorial optimization problem The 1-center problem, also known as minimax problem 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. 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 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. Another special case, the closest string problem, arises when the inputs are strings and their distance is measured using Hamming distance. The 1-center problem can be restated as finding a star 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 between two selected vertices, in place of a star, is called the minimax path problem. See also Minimum-diameter spanning tree Minsum facility location (1-median problem), with geometric median being a special case Maxmin facility location (obnoxious facility location) k-center problem k-median problem References Megiddo Nimrod The weighted Euclidean 1-center problem Mathematics of Operations Research 8 4 498–504 November 1983 http://theory.stanford.edu/~megiddo/pdf/weight1.pdf 10.1287/moor.8.4.498 Foul Abdelaziz A 1-center problem on the plane with uniformly distributed demand points Operations Research Letters 34 3 264–268 Elsevier May 2006 10.1016/j.orl.2005.04.011 Chandrasekaran R. The weighted euclidean 1-center problem Operations Research Letters 1 3 111–112 Elsevier July 1982 10.1016/0167-6377(82)90009-8 Colebrook M. J. Gutiérrez, S. Alonso J. Sicilia A New Algorithm for the Undesirable 1-Center Problem on Networks Journal of the Operational Research Society 53 12 1357–1366 Palgrave Macmillan Journals December 2002 822725 10.1057/palgrave.jors.2601468 Burkard Rainer E. Helidon Dollani A Note on the Robust 1-Center Problem on Trees Annals of Operations Research 110 1–4 69–82 Kluwer Academic Publishers February 2002 1572-9338 10.1023/A:1020711416254 Category:Combinatorial optimization