1. Introduction

Perhaps one of the first center selection problems for which there is a historical register is the following: “Given three points in the plane, find a fourth point such that the sum of its distances to the three points is minimized” ^[1]. Given its simplicity, it is hard to establish who first stated this problem. However, this problem is usually associated with Pierre de Fermat, who asked this question around 1636, and its first registered solution is associated with Evangelista Torricelli ^[1]. An extension of this problem is known as Weber’s problem, where the points have an associated cost and the goal is to locate not 1 but k points (centers) ^[1]. By adding new properties and restrictions to a basic k-center problem, the collection of k-center problems has become larger over the years.

2. Origin

One of the most basic center selection problems that more directly gave rise to many other similar problems is known as the absolute 1-center problem. This problem was formally introduced by Hakimi when he faced the problem of finding the best location for a police station in a highway system ^[2]. The goal of this problem is to minimize the distance from the farthest community to the police station. In a graph, an absolute 1-center is a location along any edge that minimizes the distance from the farthest vertex to such location. The k-center problem is a more general version of the absolute 1-center problem, where the goal is to locate k>1 centers in the graph, such that the distance from the farthest vertex to its nearest center is minimized. These centers may be located along any edge (absolute k-center) or may be restricted to vertices (vertex k-center). Besides, there can be a cost associated with the selection of every vertex (weighted vertex k-center problem) ^[3].

3. Variants

There are many other restrictions that yield different k-center problems. For instance, the following problems aim at minimizing the maximum distance from vertices to their nearest centers under different assumptions and/or restrictions:

• The asymmetric k-center problem, where the input is an asymmetric directed graph that satisfies the directed triangle inequality. The best possible polynomial algorithm for this problem delivers an O(log∗n) approximation ^[4], ^[5].
• The capacitated k-center problem, where each center can attend only a fixed number of vertices ^[6].
• The heterogeneous capacitated k-center problem, is similar to the capacitated k-center problem, except that the capacities of each center are also to be assigned ^[7].
• The aligned k-center problem is where the centers must be selected from a previously defined line or polygon ^[8].
• The edge-dilation k-center problem, where the goal is to minimize the maximum ratio of the distance between any two nodes via their respective centers to their true graph distance ^[9].
• The fault-tolerant k-center problem, where each selected center must have a set of α≤k centers close to it ^[10].
• The fault-tolerant capacitated k-center problem, where each center can attend only a fixed number of vertices, and after the failure of some centers, the vertices can be reassigned to other centers ^[11].
• The p-neighbor k-center problem, where given an integer p the goal is to minimize the maximum distance of any non-center vertex to its pth closest center ^[12].
• The k-center problem with minimum coverage, where centers are required to attend a minimum of vertices ^[13].
• The mixed k-center problem, where m centers must be in the set of vertices, and the rest can be anywhere (m<k ) ^[14].
• The p-next center problem, where the objective is to minimize the distance from the farthest vertex to its closest center plus the distance between this center to its closest alternative center ^[15].

4. Vertex k-center

Formally, the vertex k-center problem is defined as follows. Given a complete undirected graph G=(V,E) with edge costs satisfying the triangle inequality, and a positive integer k; find a subset C⊆V of centers, with |C|≤k, such that the distance from the farthest vertex v∈V to its closest center in C is minimized ^{[16][17][18][19][20]}. More specifically, the goal is to find a subset C of centers of cardinality at most k that minimizes r(C)=maxv{d(v,C)}, where d(v,C) is the distance between a vertex v and the set C, which is defined as the cost of the cheapest edge from v to any of the vertices in C. The solution size r(C) is usually known as the covering radius because in a two-dimensional Euclidean space the centers define disks that cover its nearest vertices and the radius of the larger disk is the solution size. The vertex k-center problem is perhaps the most fundamental among the k-center problems. In addition, it has potential applications in different areas, such as Facility Location ^[20][21][22], Clustering ^[23], emergency services, computer network services, distribution, and more ^[1].

Due to its importance, the vertex k-center problem has been addressed through different algorithmic approaches, such as heuristics, metaheuristics, exact algorithms, and approximation algorithms. Among these approaches, the approximation algorithms stand as the most efficient and reliable, because the vertex k-center problem can not be solved in polynomial time within an approximation factor of ρ<2, unless P=NP ^{[3][17][18][19][24][25]}. Therefore, under P≠NP, the best possible polynomial time algorithms for this problem must deliver 2-approximated solutions. To date, there are at least three known approximation algorithms that achieve this approximation factor: the Sh algorithm ^[19][26], the Gon algorithm ^[3][17], and the HS algorithm ^[18][19].

Even though the Sh, Gon, and HS algorithms achieve the best possible approximation factor (if P≠NP), they tend to perform poorly on most benchmark data sets ^[27][28][29]. For this reason, many heuristic, metaheuristic, and exact algorithms have been designed through the years. Even though these algorithms do not guarantee to converge quickly or to find optimal solutions, they find the best-known solutions (or even optimal solutions) on most benchmark data sets ^{[21][22][28][29][30][31][32][33]}. So, on one hand, there are 2-approximation algorithms, which are theoretically the best possible, but practically useless in many specific instances. On the other hand, there are heuristics that may run in polynomial time but do not give any guarantee about the quality of the generated solutions and yet may find near-optimal solutions on benchmark data sets. There are metaheuristics that do not run in polynomial time, give no guarantee on the quality of the generated solution, and yet may deliver near-optimal solutions on benchmark datasets. Finally, there are exact algorithms, that deliver the optimal solution, but give no guarantee about the termination time.

Among the polynomial heuristic algorithms are the Gr greedy pure algorithm ^[27][28], the Scr algorithm ^[28], and the CDSh algorithm ^[34]; the last two are considered the polynomial time algorithms for the vertex k-center problem with best empirical performance ^[28][29][34]. Among the exact algorithms are those proposed by Daskin ^[35], Ilhan et al. ^[36], Elloumi et al. ^[37], Al-Khedhairi and Salhi ^[38], Chen and Chen ^[39], Calik and Tansel ^[40], and Contardo et al. ^[23]. All these exact algorithms are based on Integer Programming or Mixed Integer Programming formulations. Through empirical results, these exact algorithms have shown to be relatively efficient in most instances from benchmark data sets. Among the metaheuristic algorithms are proposals based on Tabu Search ^[30], Variable Neighborhood Search ^[30][31], Scatter Search ^[21], GRASP ^[21], Memetic Genetic Algorithms ^[32], Harmony Search ^[22], and Bee Colony Optimization ^[33]. Although these methods give no guarantee of either the quality of the solutions they find or the execution time, all of them perform better than the 2-approximated Sh, Gon, and HS algorithms on most benchmark data sets reported in the literature. Because of this, we also mention a fourth approximation algorithm, the CDS algorithm ^[34], which despite having a sub-optimal approximation factor of 3, significantly outperforms the known 2-approximation algorithms over the de facto benchmark data sets from the literature.