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

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 <inline-formula> <tex-math notation="LaTeX">$C \subseteq V$ </tex-math></inline-formula> of an input graph <inline-formula> <tex-math notation="LaTeX">$G=(V,E)$ </tex-math></inline-formula>, such that the distance from the farthest vertex in <inline-formula> <tex-math notation="LaTeX">$V$ </tex-math></inline-formula> to its nearest center in <inline-formula> <tex-math notation="LaTeX">$C$ </tex-math></inline-formula> is minimized, where <inline-formula> <tex-math notation="LaTeX">$|C| \le k$ </tex-math></inline-formula>, with <inline-formula> <tex-math notation="LaTeX">$k \in Z^+$ </tex-math></inline-formula> 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 <italic>de facto</italic> benchmark data sets for the problem which includes instances of up to 71009 vertices.

Abstract licence: CC BY-NC-ND

51 more references, whose wording the paper’s licence keeps private.

A person counts once a day per paper. We keep no cookie and no address: a reader is a hash that changes every day. Any month under five reads shows no number.