Approximation Algorithms for the Vertex K-Center Problem: Survey and Experimental Evaluation

Jesus Garcia-DIaz, Rolando Menchaca-Mendez, Ricardo Menchaca-Mendez, Saul Pomares Hernandez, Julio Cesar Perez-Sansalvador, Noureddine Lakouari

Resultado de la investigación: Contribución a una revistaArtículorevisión exhaustiva

10 Citas (Scopus)

Resumen

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.

Idioma originalInglés
Número de artículo8792058
Páginas (desde-hasta)109228-109245
Número de páginas18
PublicaciónIEEE Access
Volumen7
DOI
EstadoPublicada - 2019
Publicado de forma externa

Huella

Profundice en los temas de investigación de 'Approximation Algorithms for the Vertex K-Center Problem: Survey and Experimental Evaluation'. En conjunto forman una huella única.

Citar esto