The Survey of Algorithms for k-center Problem

NAVIGATE

Table of Contents

STATISTICS

Viewed49

Downloads39

The Survey of Algorithms for k-center Problem

PDF下载 (39)

[1]WANG Xiaofeng,HUA Yingying,WANG Junxia,et al.The Survey of Algorithms for k-center Problem[J].Journal of Zhengzhou University (Engineering Science),2025,46(01):42-50.[doi:10.13705/j.issn.1671-6833.2024.01.009]

Copy

Journal of Zhengzhou University (Engineering Science)[ISSN 1671-6833/CN 41-1339/T] Volume: 46 Number of periods: 2025 01 Page number: 42-50 Column: Public date: 2024-12-23

Title:: The Survey of Algorithms for k-center Problem

Author(s):: WANG Xiaofeng¹; 2; HUA Yingying¹; WANG Junxia¹; PENG Qingyuan¹; HE Fei¹; 1.School of Computer Science and Engineering, North Minzu University, Yinchuan 750021, China; 2.The Key Laboratory of Images and Graphics Intelligent Processing of State Ethnic Affairs Commission, North Minzu University, Yinchuan 750021, China

Keywords:: k-center problem; exact algorithm; approximation algorithm; bee colony optimization algorithm; genetic algorithm

CLC:: TP301

DOI:: 10.13705/j.issn.1671-6833.2024.01.009

Abstract:: The k-center problem is fundamental in facility siting, and is also an NP-hard problem with practical applications in the fields of distribution, emergency services, etc. However, with the expansion of the problem scale, the original algorithms were no longer applicable and should be further optimized or improved. In order to find an efficient algorithm to solve the problem, the existing algorithms were studied. The algorithms for the k-center problem were classified into exact algorithms, heuristic algorithms, meta-heuristic algorithms, approximation algorithms, etc. The algorithms were compared in terms of their principles, ideas for improvement, performance, accuracy, etc. The exact algorithm obtained the optimal solution in polynomial time when solving small-scale k-center problems, but was inefficient and not applicable to large-scale problems. The heuristic algorithm could give the relative optimal solution in polynomial time, but there was no theoretical guarantee to measure the relationship with the most optimal solution. The meta-heuristic algorithm could be improved according to the existing intelligent optimization algorithms to give the relative optimal solution, but the quality of the solution could not be guaranteed. The solution obtained by using the approximation algorithm had the guarantee of the approximation ratio, which was of greater theoretical research value, but the practical value was weaker. At present, the meta-heuristic algorithm for solving the k-center problem achieved certain research results, but there were still breakthroughs in the solution time, solution scale and algorithm efficiency, which could be the focus of the future research on the k-center problem.

References:: [1]KARIV O, HAKIMI S L. An algorithmic approach to network location problems. I: the p-centers[J]. SIAM Journal on Applied Mathematics, 1979, 37(3): 513-538.
[2]DASKIN M. Network and discrete location: models, algorithms and applications[J]. Journal of the Operational Research Society, 1997, 48(7): 763-764.
[3]ZHANG F Z, HE Y C, OUYANG H B, et al. A fast and efficient discrete evolutionary algorithm for the uncapacitated facility location problem[J]. Expert Systems with Applications, 2023, 213: 118978.
[4]KAVEH A, NASR H. Solving the conditional and unconditional-center problem with modified harmony search: a real case study[J]. Scientia Iranica, 2011, 18(4): 867-877.
[5]CONTARDO C, IORI M, KRAMER R. A scalable exact algorithm for the vertex p-center problem[J]. Computers & Operations Research, 2019, 103: 211-220.
[6]GUI Z P, SUN Y Z, YANG L, et al. LSI-LSTM: an attention-aware LSTM for real-time driving destination prediction by considering location semantics and location importance of trajectory points[J]. Neurocomputing, 2021, 440: 72-88.
[7]WANG S H, GAO S, FENG X, et al. A context-based geoprocessing framework for optimizing meetup location of multiple moving objects along road networks[J]. International Journal of Geographical Information Science, 2018, 32(7): 1368-1390.
[8]ZHOU L, WANG S H, XU Z B. A multi-factor spatial optimization approach for emergency medical facilities in Beijing[J]. ISPRS International Journal of Geo-Information, 2020, 9(6): 361.
[9]ZHU Y S, DU Q Y, TIAN F, et al. Location optimization using a hierarchical location-allocation model for trauma centers in Shenzhen, China[J]. ISPRS International Journal of Geo-Information, 2016, 5(10): 190.
[10] HAN B, HU M X, ZHENG J M, et al. Site selection of fire stations in large cities based on actual spatiotemporal demands: a case study of Nanjing city[J]. ISPRS International Journal of Geo-Information, 2021, 10(8): 542.
[11] FARAHANI R Z, HEKMATFAR M. Facility location: concepts, models, algorithms and case studies[M]. Heidelberg: Physica-Verlag HD, 2009.
[12] HOCHBAUM D S, SHMOYS D B. A best possible heuristic for the k-center problem[J]. Mathematics of Operations Research, 1985, 10(2): 180-184.
[13] DYER M E, FRIEZE A M. A simple heuristic for the pcentre problem[J]. Operations Research Letters, 1985, 3(6): 285-288.
[14] PANIGRAHY R, VISHWANATHAN S. An O(log∗n) approximation algorithm for the asymmetric p-center problem[J]. Journal of Algorithms, 1998, 27(2): 259-268.
[15] KHULLER S, SUSSMANN Y J. The capacitated K-center problem[J]. SIAM Journal on Discrete Mathematics, 2000, 13(3): 403-418.
[16] BRASS P, KNAUER C, NA H S, et al. The aligned kcenter problem[J]. International Journal of Computational Geometry & Applications, 2011, 21(2): 157-178.
[17] KHULLER S, PLESS R, SUSSMANN Y J. Fault tolerant K-center problems[J]. Theoretical Computer Science, 2000, 242(1/2): 237-245.
[18] LIM A, RODRIGUES B, WANG F, et al. k-center problems with minimum coverage[J]. Theoretical Computer Science, 2005, 332(1/2/3): 1-17.
[19] XU Y, PENG J G, XU Y F. The mixed center location problem[J]. Journal of Combinatorial Optimization, 2018, 36(4): 1128-1144.
[20] MINIEKA E. The m-center problem[J]. SIAM Review, 1970, 12(1): 138-139.
[21] DASKIN M S. A new approach to solving the vertex pcenter problem to optimality: algorithm and computational results[J]. Communications of the Operations Research Society of Japan, 2000, 45(9): 428-436.
[22] ILHAN T, PINAR M C. An efficient exact algorithm for the vertex p-center problem[EB/OL]. (2001-09-27) [2023-12-30]. https:∥optimization-online. org/2001/09/376/ .
[23] AL-KHEDHAIRI A, SALHI S. Enhancements to two exact algorithms for solving the vertex P-center problem [J]. Journal of Mathematical Modelling and Algorithms, 2005, 4(2): 129-147.
[24] MLADENOVIC’ N, LABBÉ M, HANSEN P. Solving the p-center problem with tabu search and variable neighborhood search[J]. Networks, 2003, 42(1): 48-64.
[25] PACHECO J A, CASADO S. Solving two location models with few facilities by using a hybrid heuristic: a real health resources case[J]. Computers & Operations Research, 2005, 32(12): 3075-3091.
[26] GLOVER F. Future paths for integer programming and links to artificial intelligence[J]. Computers & Operations Research, 1986, 13(5): 533-549.
[27] GLOVER F, LAGUNA M. Tabu search[M]. New York: Springer Science+Business Media, 1997.
[28] LAGUNA M, MARTÍ R. Scatter search: methodology and implementations in C[J]. Interfaces, 2006, 36(6): 610-612.
[29]蒋建林, 徐进澎, 文杰. 基于单亲遗传模拟退火算法的顶点p-中心问题[J]. 系统工程学报, 2011, 26 (3): 414-420.
JIANG J L, XU J P, WEN J. Solving the vertex p-center problem with a partheno-genetic simulated annealing algorithm[J]. Journal of Systems Engineering, 2011, 26 (3): 414-420.
[30] DAVIDOVIC’ T, RAMLJAK D, ŠELMIC’ M, et al. Bee colony optimization for the p-center problem[J]. Computers & Operations Research, 2011, 38(10): 1367-1376.
[31] YURTKURAN A, EMEL E. A modified artificial bee colony algorithm for p-center problems[J]. The Scientific World Journal, 2014, 2014: 824196.
[32]包敏泽, 胡秀婷, 谢玉莹, 等. 基于人工蜂群算法的p-center问题求解算法[J]. 计算机工程与科学, 2020, 42(6): 1127-1133.
BAO M Z, HU X T, XIE Y Y, et al. A p-center problem solving algorithm based on artificial bee colony algorithm [J]. Computer Engineering and Science, 2020, 42(6): 1127-1133.
[33] LUˇ CIC’ P, TEODOROVIC’ D. Bee system: modeling combinatorial optimization transportation engineering problems by swarm intelligence[C]∥The TRISTAN IV Triennial Symposium on Transportation Analysis. Sao Miguel: TRISTAN, 2001: 441-445.
[34] LUˇ CIC’ P, TEODOROVIC’ D. Transportation modeling: an artificial life approach[C]∥14th IEEE International Conference on Tools with Artificial Intelligence(ICTAI 2002). Piscataway: IEEE, 2003: 216-223.
[35] LUˇ CIC’ P, TEODOROVIC’ D. Computing with bees: attacking complex transportation engineering problems[J]. International Journal on Artificial Intelligence Tools, 2003, 12(3): 375-394.
[36]王守娜, 刘弘, 高开周. 一种应用于函数优化问题的多种群人工蜂群算法[J]. 郑州大学学报(工学版), 2018, 39(6):30-35.
WANG S N, LIU H, GAO K Z. A multi-swarm artificial bee colony algorithm for function optimization[J]. Journal of Zhengzhou University (Engineering Science), 2018, 39(6):30-35.
[37]何尧, 刘建华, 杨荣华. 人工蜂群算法研究综述[J]. 计算机应用研究, 2018, 35(5): 1281-1286.
HE Y, LIU J H, YANG R H. Survey on artificial bee colony algorithm[J]. Application Research of Computers, 2018, 35(5): 1281-1286.
[38] RANA R, GARG D. The analytical study of k-center problem solving techniques[J]. International Journal of Information Technology and Knowledge Management, 2008, 1(2): 527-535.
[39] SHMOYS D B. Computing near-optimal solutions to combinatorial optimization problems[M]∥DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Providence: American Mathematical Society, 1995: 355397.
[40] PLESNÍK J. A heuristic for the p-center problems in graphs[J]. Discrete Applied Mathematics, 1987, 17 (3): 263-268.
[41] GONZALEZ T F. Clustering to minimize the maximum intercluster distance[J]. Theoretical Computer Science, 1985, 38: 293-306.
[42] GARCIA-DIAZ J, SANCHEZ-HERNANDEZ J, MENCHACA-MENDEZ R, et al. When a worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem[J]. Journal of Heuristics, 2017, 23(5): 349-366.
[43] MIHELI ˇ C J, ROBI ˇ C B. Solving the k-center problem efficiently with a dominating set algorithm[J]. Journal of Computing and Information Technology, 2005, 13(3): 225-233.
[44] BEASLEY J E. OR-library: distributing test problems by electronic mail[J]. Journal of the Operational Research Society, 1990, 41(11): 1069-1072.
[45] REINELT G. TSPLIB—A traveling salesman problem library[J]. ORSA Journal on Computing, 1991, 3(4): 376-384.
[46] GARCIA-DIAZ J, MENCHACA-MENDEZ R, MENCHACA-MENDEZ R, et al. Approximation algorithms for the vertex k-center problem: survey and experimental evaluation[J]. IEEE Access, 2019, 7: 109228-109245.

Similar References:

Memo

Last Update: 2024-12-30