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.

• Publication year

  2019

• Venue

  IEEE Access

• Publication date

  2019-08-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/ACCESS.2019.2933875
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• GRASP and VNS for solving the p-next center problem

  2019cited by this paper
• A scalable exact algorithm for the vertex p-center problem

  2018influential reference
• When a worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem

  2017cited by this paper
• The Heterogeneous Capacitated k-Center Problem

  2016cited by this paper
• The mixed center location problem

  2016cited by this paper
• Hybrid meta-heuristics with VNS and exact methods: application to large unconditional and conditional vertex p\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\

  2015cited by this paper
• Double bound method for solving the p-center location problem

  2013cited by this paper
• The Fault Tolerant Capacitated k-Center Problem

  2012cited by this paper
• Solving the Connected Dominating Set Problem and Power Dominating Set Problem by Integer Programming

  2012cited by this paper
• The Aligned k-Center Problem

  2011cited by this paper
• Solving the conditional and unconditional p-center problem with modified harmony search: A real case study

  2011cited by this paper
• New relaxation-based algorithms for the optimal solution of the continuous and discrete p-center problems

  2009influential reference
• Facility location: concepts, models, algorithms and case studies

  2009cited by this paper
• A Memetic Genetic Algorithm for the Vertex p-center Problem

  2008cited by this paper
• A note on the complexity of minimum dominating set

  2006cited by this paper
• Asymmetric k-center is log* n-hard to approximate

  2005cited by this paper
• Solving the k-center Problem Efficiently with a Dominating Set Algorithm

  2005cited by this paper
• Solving two location models with few facilities by using a hybrid heuristic: a real health resources case

  2005cited by this paper
• Enhancements to Two Exact Algorithms for Solving the Vertex P-Center Problem

  2005cited by this paper
• k-Center problems with minimum coverage

  2004cited by this paper
• A New Formulation and Resolution Method for the p-Center Problem

  2004cited by this paper
• An approximation algorithm for the edge-dilation k-center problem,

  2004cited by this paper
• The Capacitated K-Center Problem

  2000cited by this paper
• Solving the p‐Center problem with Tabu Search and Variable Neighborhood Search

  2000cited by this paper
• The p-Neighbor k-Center Problem

  1998cited by this paper
• Fault tolerant K-center problems

  1997cited by this paper
• Approximation Algorithms for NP-Hard Problems

  1997cited by this paper
• An O(log*n) approximation algorithm for the asymmetric p-center problem

  1996cited by this paper
• Network and Discrete Location: Models, Algorithms, and Applications

  1995influential reference
• Computing near-optimal solutions to combinatorial optimization problems

  1994cited by this paper
• TSPLIB - A Traveling Salesman Problem Library

  1991influential reference
• OR-Library: Distributing Test Problems by Electronic Mail

  1990influential reference
• A heuristic for the p-center problems in graphs

  1987influential reference
• Clustering to Minimize the Maximum Intercluster Distance

  1985influential reference
• A Best Possible Heuristic for the k-Center Problem

  1985influential reference
• A simple heuristic for the p-centre problem

  1985influential reference
• The NP-Completeness Column: An Ongoing Guide

  1982cited by this paper
• An Algorithmic Approach to Network Location Problems. II: The p-Medians

  1979cited by this paper
• An Algorithmic Approach to Network Location Problems. I: The p-Centers

  1979cited by this paper
• Easy and hard bottleneck location problems

  1979cited by this paper
• The m-Center Problem

  1970cited by this paper
• Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph

  1964cited by this paper
• Algorithm 97: Shortest path

  1962cited by this paper
• A Theorem on Boolean Matrices

  1962cited by this paper

• p-Center Problem

  2025cites this paper
• Accelerating Image Classification with Graph Convolutional Neural Networks using Voronoi Diagrams

  2025cites this paper
• A graph attention-based policy gradient method with an adaptive embedding strategy for k-center problems

  2025cites this paper
• AlphaZeroES: Direct score maximization outperforms planning loss minimization

  2024cites this paper
• On the nested p-center problem

  2024cites this paper
• In-situ elastic calibration of robots: Minimally-invasive technology, cover-based pose search and aerospace case studies

  2024cites this paper
• A greedy heuristic for graph burning

  2024cites this paper
• A Spectral Gap-Based Topology Control Algorithm for Wireless Backhaul Networks

  2024cites this paper
• Mixed‐Integer Linear Programming Approaches for Nested p$$ p $$ ‐Center Problems With Absolute and Relative Regret Objectives

  2024cites this paper
• An artificial bee colony algorithm for the minimum edge-dilation K-center problem

  2024cites this paper
• A Constructive Heuristic for the Uniform Capacitated Vertex k-center Problem

  2023influential citation
• Cold PAWS: Unsupervised class discovery and the cold-start problem

  2023cites this paper
• Cold PAWS: Unsupervised class discovery and addressing the cold-start problem for semi-supervised learning

  2023cites this paper
• A vertex weighting-based double-tabu search algorithm for the classical p-center problem

  2023cites this paper
• An Iterated Local Search for the Minimum Edge-Dilation K-Center Problem

  2023cites this paper
• Leasing K-Center, nova restrição e abordagem heurística

  2022cites this paper
• Design of an Optimal Testbed for Acoustic Tags: Test Case for Marine Megafauna

  2022cites this paper
• A Global Optimization Algorithm for K-Center Clustering of One Billion Samples

  2022influential citation
• Graph Burning: Mathematical Formulations and Optimal Solutions

  2022cites this paper
• Fiberwise dimensionality reduction of topologically complex data with vector bundles

  2022cites this paper
• A Trade-Off Algorithm for Solving p-Center Problems with a Graph Convolutional Network

  2022influential citation
• A scaleable projection-based branch-and-cut algorithm for the p-center problem

  2021cites this paper
• Solving the Capacitated Vertex K-Center Problem through the Minimum Capacitated Dominating Set Problem

  2020influential citation
• A 3 − 2 /b ( G ) - APPROXIMATION ALGORITHM FOR THE GRAPH BURNING PROBLEM

  2020cites this paper
• Burning Graphs Through Farthest-First Traversal

  2020cites this paper
• A Survey of Emergency Service Facilities Site Selection (ESFSS) Algorithms

  2020cites this paper
• Approximation Algorithm-Based Prosumer Scheduling for Microgrids

  2020cites this paper
• The Meet-in-the-Middle k -Center Problem

  year unknowncites this paper