TY - JOUR

T1 - Approximation Algorithms for the Vertex K-Center Problem

T2 - Survey and Experimental Evaluation

AU - Garcia-DIaz, Jesus

AU - Menchaca-Mendez, Rolando

AU - Menchaca-Mendez, Ricardo

AU - Pomares Hernandez, Saul

AU - Perez-Sansalvador, Julio Cesar

AU - Lakouari, Noureddine

N1 - Publisher Copyright:
© 2013 IEEE.

PY - 2019

Y1 - 2019

N2 - The vertex k-center problem is a classical NP-Hard optimization problem with application to Facility Location and Clustering among others. This problem consists in finding a subset C ⫅ V of an input graph G = (V, E), such that the distance from the farthest vertex in V to its nearest center in C is minimized, where iCi <; k, with k ϵ Z± as part of the input. Many heuristics, metaheuristics, approximation algorithms, and exact algorithms have been developed for this problem. This paper presents an analytical study and experimental evaluation of the most representative approximation algorithms for the vertex k-center problem. For each of the algorithms under consideration and using a common notation, we present proofs of their corresponding approximation guarantees as well as examples of tight instances of such approximation bounds, including a novel tight example for a 3-approximation algorithm. Lastly, we present the results of extensive experiments performed over de facto benchmark data sets for the problem which includes instances of up to 71009 vertices.

AB - The vertex k-center problem is a classical NP-Hard optimization problem with application to Facility Location and Clustering among others. This problem consists in finding a subset C ⫅ V of an input graph G = (V, E), such that the distance from the farthest vertex in V to its nearest center in C is minimized, where iCi <; k, with k ϵ Z± as part of the input. Many heuristics, metaheuristics, approximation algorithms, and exact algorithms have been developed for this problem. This paper presents an analytical study and experimental evaluation of the most representative approximation algorithms for the vertex k-center problem. For each of the algorithms under consideration and using a common notation, we present proofs of their corresponding approximation guarantees as well as examples of tight instances of such approximation bounds, including a novel tight example for a 3-approximation algorithm. Lastly, we present the results of extensive experiments performed over de facto benchmark data sets for the problem which includes instances of up to 71009 vertices.

KW - Approximation algorithms

KW - k-center problem

KW - polynomial time heuristics

UR - http://www.scopus.com/inward/record.url?scp=85091345650&partnerID=8YFLogxK

U2 - 10.1109/ACCESS.2019.2933875

DO - 10.1109/ACCESS.2019.2933875

M3 - Artículo

AN - SCOPUS:85091345650

VL - 7

SP - 109228

EP - 109245

JO - IEEE Access

JF - IEEE Access

SN - 2169-3536

M1 - 8792058

ER -