Submitted Successfully!
To reward your contribution, here is a gift for you: A free trial for our video production service.
Thank you for your contribution! You can also upload a video entry or images related to this topic.
Version Summary Created by Modification Content Size Created at Operation
1 -- 1395 2023-11-28 23:07:28 |
2 one word changed Meta information modification 1395 2023-11-28 23:14:30 | |
3 format correct Meta information modification 1395 2023-11-30 03:16:56 |

Do you have a full video?

# Confirm

Are you sure to Delete?
Cite
García Díaz, J. K-Center Problem. Encyclopedia. Available online: https://encyclopedia.pub/entry/52164 (accessed on 08 August 2024).
García Díaz J. K-Center Problem. Encyclopedia. Available at: https://encyclopedia.pub/entry/52164. Accessed August 08, 2024.
García Díaz, Jesús. "K-Center Problem" Encyclopedia, https://encyclopedia.pub/entry/52164 (accessed August 08, 2024).
García Díaz, J. (2023, November 28). K-Center Problem. In Encyclopedia. https://encyclopedia.pub/entry/52164
García Díaz, Jesús. "K-Center Problem." Encyclopedia. Web. 28 November, 2023.
K-Center Problem

This entry is adapted from the peer-reviewed paper 10.1109/ACCESS.2019.2933875

K-center problems are particular cases of the facility location problem, where a set of optimal centers are to be found given a set of constraints. In a nutshell, a k-center problem usually seeks a set of at most k centers that minimize the distance a client must travel to its nearest center. Namely, their objective function is often a minmax one. Naturally, these problems are well suited for modeling real location problems. Although many different problems fit within the description of a k-center problem, the most popular of these is the vertex k-center problem, where the input is a simple graph and an integer k, and the goal is to find at most k vertices whose distance to the remaining vertices is minimal.

k-center facility location

## 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(logn) 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 CV of centers, with |C|k, such that the distance from the farthest vertex vV 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 PNP, 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 PNP), 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.

### References

1. Maryam Biazaran and Bahareh SeyediNezhad. Facility Location: Concepts Models Algorithms and Case Studies; Farahani, Reza Zanjirani and Hekmatfar, Masoud, Eds.; Springer: Heidelberg, Germany, 2009; pp. 0.
2. S. L. Hakimi Optimum locations of switching centers and the absolute centers and medians of a graph. Oper. Res. 1964, 12, 450-459.
3. M. E. Dyer and A. M. Frieze A simple heuristic for the p-centre problem. Oper. Res. Lett. 1985, 3, 285-288.
4. J. Chuzhoy, S. Guha, E. Halperin, S. Khanna, G. Kortsarz, R. Krauthgamer, et al., "Asymmetric k-center is log* n-hard to approximate", Proc. 36th Annu. ACM Symp. Theory Comput. (STOC), pp. 538-551, 2004.
5. S. Vishwanathan, "An O(log*n) approximation algorithm for the asymmetric p-center problem", Proc. 7th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA), pp. 1-5, 1996.
6. S. Khuller and Y. J. Sussmann The capacitated k-center problem. SIAM J. Discrete Math. 2000, 13, 403-418.
7. D. Chakrabarty, R. Krishnaswamy and A. Kumar, "The heterogeneous capacitated k-center problem", Proc. Int. Conf. Integer Program. Combinat. Optim., pp. 123-135, 2017.
8. P. Brass, C. Knauer, H.-S. Na, C.-S. Shin and A. Vigneron The aligned k-center problem. Int. J. Comput. Geometry Appl. 2011, 21, 157-178.
9. J. Könemann, Y. Li, O. Parekh and A. Sinha An approximation algorithm for the edge-dilation k-center problem. Oper. Res. Lett. 2004, 32, 491-495.
10. S. Khuller, R. Pless and Y. J. Sussmann Fault tolerant k -center problems. Theor. Comput. Sci. 2000, 242, 237-245.
11. S. Chechik and D. Peleg The fault-tolerant capacitated k -center problem. Theor. Comput. Sci. 2015, 566, 12-25.
12. S. Chaudhuri, N. Garg and R. Ravi The p -neighbor k-center problem. Inf. Process. Lett. 1998, 65, 131-134.
13. A. Lim, B. Rodrigues, F. Wang and Z. Xu k-center problems with minimum coverage. Theor. Comput. Sci. 2005, 332, 1-17.
14. Y. Xu, J. Peng and Y. Xu The mixed center location problem. Combinatorial Optimization and Applications 2016, 10043, 0.
15. A. D. López-Sánchez, J. Sánchez-Oro and A. G. Hernández-Díaz GRASP and VNS for solving the p -next center problem. Comput. Oper. Res. 2019, 104, 295-303.
16. O. Kariv and S. L. Hakimi An algorithmic approach to network location problems. I: The p-centers. SIAM J. Appl. Math. 1979, 37, 513-538.
17. T. F. Gonzalez Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 1985, 38, 293-306.
18. D. S. Hochbaum and D. B. Shmoys A best possible heuristic for the k-center problem. Math. Oper. Res. 1985, 10, 180-184.
19. J. Plesník A heuristic for the p-center problems in graphs. Discrete Appl. Math. 1987, 17, 263-268.
20. M. S. Daskin, Network and Discrete Location: Models Algorithms and Applications, Hoboken, NJ, USA:Wiley, 2011.
21. J. A. Pacheco and S. Casado Solving two location models with few facilities by using a hybrid heuristic: A real health resources case. Comput. Oper. Res. 2005, 32, 3075-3091.
22. A. Kaveh and H. Nasr Solving the conditional and unconditional p-center problem with modified harmony search: A real case study. Scientia Iranica 2011, 18, 867-877.
23. C. Contardo, M. Iori and R. Kramer A scalable exact algorithm for the vertex p-center problem. Comput. Oper. Res. 2019, 103, 211-220.
24. D. S. Hochbaum, Approximation Algorithms for NP-Hard Problems, Boston, MA, USA:PWS, 1997.
25. W.-L. Hsu and G. L. Nemhauser Easy and hard bottleneck location problems. Discrete Appl. Math. 1979, 1, 209-215.
26. , "Computing near-optimal solutions to combinatorial optimization problems" in Combinatorial Optimization, AMS Publications, pp. 355-397, 1995.
27. R. Rana and D. Garg The analytical study of k-center problem solving techniques. Int. J. Inf. Technol. Knowl. Manage. 2008, 1, 527-535.
28. B. Robić and J. Mihelić Solving the k-center problem efficiently with a dominating set algorithm. J. Comput. Inf. Technol. 2005, 13, 225-234.
29. J. G. Diaz, R. M. Mendez, R. M. Mendez and R. Quintero A structure-driven randomized algorithm for the K -center problem. IEEE Latin Amer. Trans. 2015, 13, 746-752.
30. N. Mladenović, M. Labbé and P. Hansen Solving the p-center problem with tabu search and variable neighborhood search. Netw. Int. J. 2003, 42, 48-64.
31. C. A. Irawan, S. Salhi and Z. Drezner Hybrid meta-heuristics with VNS and exact methods: Application to large unconditional and conditional vertex p-centre problems. J. Heuristics 2016, 22, 507-537.
32. W. Pullan A memetic genetic algorithm for the vertex p-center problem. Evol. Comput. 2008, 16, 417-436.
33. T. Davidović, D. Ramljak, M. Šelmić and D. Teodorović Bee colony optimization for the p-center problem. Comput. Oper. Res. 2011, 38, 1367-1376.
34. J. Garcia-Diaz, J. Sanchez-Hernandez, R. Menchaca-Mendez and R. Menchaca-Mendez When a worse approximation factor gives better performance: A 3-approximation algorithm for the vertex k-center problem. J. Heuristics 2018, 23, 349-366.
35. M. S. Daskin A new approach to solving the vertex p-center problem to optimality: Algorithm and computational results. Commun. Oper. Res. Soc. Jpn. 2000, 45, 428-436.
36. , "An efficient exact algorithm for the vertex p-center problem and computational experiments for different set covering subproblems", 2002.
37. S. Elloumi, M. Labbé and Y. Pochet A new formulation and resolution method for the p-center problem. INFORMS J. Comput. 2004, 16, 84-94.
38. A. Al-Khedhairi and S. Salhi Enhancements to two exact algorithms for solving the vertex P-center problem. J. Math. Model. Algorithms 2005, 4, 129-147.
39. D. Chen and R. Chen New relaxation-based algorithms for the optimal solution of the continuous and discrete p-center problems. Comput. Oper. Res. 2009, 36, 1646-1655.
40. H. Calik and B. C. Tansel Double bound method for solving the p -center location problem. Comput. Oper. Res. 2013, 40, 2991-2999.
More
Information
Subjects:
Contributor MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register :
View Times: 382
Revisions: 3 times (View History)
Update Date: 30 Nov 2023
1000/1000