arXiv preprint ·
An experimental evaluation of static k-center clustering algorithms on graphs
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
The $k$-center problem is one of the most fundamental clustering problems and has applications in a wide range of areas, including facility location, network design, data mining, and machine learning. Given a set of objects together with a distance measure, the goal is to select $k$ centers such that the maximum distance from any object to its closest center is minimized. The $k$-center problem has been studied extensively from a theoretical perspective, both in metric spaces and on graphs. While there have been experimental studies for $k$-center clustering in metric spaces, a comprehensive experimental comparison of graph-based $k$-center algorithms on large-scale graphs is still lacking. In this paper, we bridge this gap by evaluating a set of algorithms ranging from classical approaches such as Gonzalez's greedy algorithm [TCS 1985], an algorithm based on the framework established by Hochbaum and Shmoys [Math. Oper. Res. 1985], to more recent methods, including algorithms by Thorup [SICOMP 2001] and Abboud et al. [SOSA 2023]. Our study considers both running time, solution quality and the effects of parallelism on a variety of synthetic and real-world datasets. Our goal is to provide a comprehensive comparison of state-of-the-art $k$-center algorithms on graphs and identify the strengths and weaknesses of different approaches in practice.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Near-Optimal Consistency-Robustness Bounds for Non-Clairvoyant Scheduling
Optimal Mixing for Local Edge-Coloring Dynamics on Trees
Optimal Labeling Schemes for $Γ$-Free Matrices
Report the tolerance, not the count: exact phylogenetic distance deconvolution with incomplete references
On the Largest Cardinality Subset Sum
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.